Merge Sort
Merge sort is the sorting algorithm that follows the divide and conquer technique. It is a popular and efficient sorting algorithm.
It splits the given list into two equal list i.e. sub-list. calls itself for the two lists and then merges the two sorted list.
The process of splitting and merging can be carried out recursively till there is only element in the list.
An array with single element is alway sorted.
Time Complexity
| Case | Time Complexity |
|---|---|
| Best Case | O(n log n) |
| Average Case | O(n log n) |
| Worst Case | O(n log n) |
- Best Case O(n log n):It occurs when there is no sorting needed, i.e. the array is already sorted.
- Average Case O(n log n): The array elements are in a jumbled order that is not properly ascending and descending.
- Worst Case O(n log n): This occurs when the array elements need to be sorted in reverse order.
Space Complexity
| Space Complexity | O(n) |
| Stable | Yes |
- A merge sort required extra variables for swapping. Hence, the space complexity of merge sorting is
O(n).
Merge Sort
#include <stdio.h>
/* Function to merge the subarrays of a[] */
void merge(int a[], int beg, int mid, int end) {
int i, j, k;
int n1 = mid - beg + 1;
int n2 = end - mid;
//temporary arrays
int leftArray[n1], rightArray[n2];
/* copy data to temp arrays */
for (int i = 0; i < n1; i++)
leftArray[i] = a[beg + i];
for (int j = 0; j < n2; j++)
rightArray[j] = a[mid + 1 + j];
i = 0; /* initial index of first sub-array */
j = 0; /* initial index of second sub-array */
k = beg; /* initial index of merged sub-array */
while (i < n1 && j < n2) {
if(leftArray[i] <= rightArray[j]) {
a[k] = leftArray[i];
i++;
} else {
a[k] = rightArray[j];
j++;
}
k++;
}
while (i < n1) {
a[k] = leftArray[i];
i++;
k++;
}
while (j < n2) {
a[k] = rightArray[j];
j++;
k++;
}
}
void mergeSort(int a[], int beg, int end) {
if (beg < end) {
int mid = (beg + end) / 2;
mergeSort(a, beg, mid);
mergeSort(a, mid + 1, end);
merge(a, beg, mid, end);
}
}
/* Function to print the array */
void print(int a[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}
int main() {
int a[] = { 50, 20, 32, 13, 30, 18, 17, 40, 42 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
print(a, n);
mergeSort(a, 0, n - 1);
printf("After sorting array elements are - \n");
print(a, n);
return 0;
}class MergeSort {
/* Function to merge the subarrays of a[] */
static void merge(int a[], int beg, int mid, int end) {
int i, j, k;
int n1 = mid - beg + 1;
int n2 = end - mid;
/* temporary Arrays */
int leftArray[] = new int[n1];
int rightArray[] = new int[n2];
/* copy data to temp arrays */
for (i = 0; i < n1; i++)
leftArray[i] = a[beg + i];
for (j = 0; j < n2; j++)
rightArray[j] = a[mid + 1 + j];
i = 0; /* initial index of first sub-array */
j = 0; /* initial index of second sub-array */
k = beg; /* initial index of merged sub-array */
while (i < n1 && j < n2) {
if(leftArray[i] <= rightArray[j]) {
a[k] = leftArray[i];
i++;
} else {
a[k] = rightArray[j];
j++;
}
k++;
}
while (i < n1) {
a[k] = leftArray[i];
i++;
k++;
}
while (j < n2) {
a[k] = rightArray[j];
j++;
k++;
}
}
static void mergeSort(int a[], int beg, int end) {
if (beg < end) {
int mid = (beg + end) / 2;
mergeSort(a, beg, mid);
mergeSort(a, mid + 1, end);
merge(a, beg, mid, end);
}
}
/* Function to print the array */
static void print(int a[], int n) {
for (int i = 0; i < n; i++)
System.out.print(a[i] + " ");
}
public static void main(String args[]) {
int a[] = { 50, 20, 32, 13, 30, 18, 17, 40, 42 };
int n = a.length;
System.out.println("\nBefore sorting array elements are - ");
print(a, n);
mergeSort(a, 0, n - 1);
System.out.println("\nAfter sorting array elements are - ");
print(a, n);
System.out.println("");
}
}Advantages
- It has a timing complexity of O (n log n).
- It can be used for both internal and external sorting.
- It is a stable sorting algorithm.
Disadvantages
- It requires an additional memory for sorting of merged data during merging phase.