Merge sort is another comparison based sorting algorithm. Also, it is a divide and conquer algorithm, which means the problem is split into multiple simplest problems and the final solution is represented by putting together all the solutions.
How it works:
The algorithm divides the unsorted list into two sub-lists of about half the size. Then sort each sub-list recursively by re-applying the merge sort and then merge the two sub-lists into one sorted list.
Step by step example :
Having the following list, let’s try to use merge sort to arrange the numbers from lowest to greatest:
Unsorted list: 50, 81, 56, 32, 44, 17, 99
Divide the list in two: the first list is 50, 81, 56, 32 and the second is 44, 17, 99 .
Divide again the first list in two which results: 50, 81 and 56, 32.
Divide one last time, and will result in the elements of 50 and 81. The element of 50 is just one, so you could say it is already sorted. 81 is the same one element so it’s already sorted.
Now, It is time to merge the elements together, 50 with 81, and it is the proper order.
The other small list, 56, 32 is divided in two, each with only one element. Then, the elements are merged together, but the proper order is 32, 56 so these two elements are ordered.
Next, all these 4 elements are brought together to be merged: 50, 81 and 32, 56. At first, 50 is compare to 32 and is greater so in the next list 32 is the first element: 32 * * *. Then 50 is again compared to 56 and is smaller, so the next element is 50: 32 50 * *. The next element is 81, which is compared to 56, and being greater, 56 comes before, 32 50 56 *, and the last element is 81, so the list sorted out is 32 50 56 81.
We do the same thing or the other list, 44, 17, 99, and after merging the sorted list will be: 17, 44, 99.
The final two sub-lists are merged in the same way: 32 is compared to 17, so the latter comes first: 17 * * * * * *. Next, 32 is compared to 44, and is smaller so it ends up looking like this : 17 32 * * * * *. This continues, and in the end the list will be sorted.
Sample code:
#include < iostream >using namespace std;
void Merge(int *a, int low, int mid, int high)
{int i = low, j = mid + 1, k = low;
int b[100];
while ((i <= mid) && (j <= high))
{if (a[i] < a[j])
{b[k] = a[i];
i++;
}else{b[k] = a[j];
j++;
}k++;
}while (i <= mid)
{b[k] = a[i];
i++;
k++;
}while (j <= high)
{b[k] = a[j];
j++;
k++;
}for (k = low; k <= high; k++)
a[k] = b[k];
}void MergeSort(int *a, int low, int high)
{int mid;
if(low >= high)
return;
else{mid =(low + high) / 2;
MergeSort(a, low, mid);
MergeSort(a, mid+1, high);
Merge(a, low, mid, high);
}}int main()
{int *a;
int n;
cout << "The number of elements is: ";
cin>>n;
a = (int*) calloc (n,sizeof(int));
for(int i=0;i < n;i++)
{cout << "Input " << i << " element: ";
cin >> a[i]; // Adding the elements to the array
}cout << "nUnsorted list:" << endl; // Displaying the unsorted array
for(int i=0;i < n;i++)
{cout << a[i] << " ";
}MergeSort(a, 0, n-1);
cout<<"nThe sorted list is: " << endl;
for (int i=0;i < n;i++)
cout << a[i] << " ";
return 0;
}
Output:
Code explanation:
The MergeSort procedure splits recursively the lists into two smaller sub-lists. The merge procedure is putting back together the sub-lists, and at the same time it sorts the lists in proper order, just like in the example from above.
Complexity:
Merge sort guarantees O(n*log(n)) complexity because it always splits the work in half. In order to understand how we derive this time complexity for merge sort, consider the two factors involved: the number of recursive calls, and the time taken to merge each list together..
Advantages:
- is stable;
- It can be applied to files of any size.
- Reading through each run during merging and writing the sorted record is also sequential. The only seeking necessary is as we switch from run to run.
Disadvantages:
- it requires an extra array;
- is recursive;
Conclusion:
Merge sort is a stable algorithm that performs even faster than heap sort on large data sets. Also, due to use of divide-and-conquer method merge sort parallelizes well. The only drawback could be the use of recursion, which could give some restrictions to limited memory machines.
