Merge Sort
Merge Sort is essentially an algorithm similar to Quick Sort, using the Divide and Conquer strategy. It splits the input array in half equally first. After that, those are mixing in an ordered way.
An example of Merge Sort
If A = [7, 5 ,9, 3, 6, 2, 0, 4]
[7, 5, 9, 3, 6, 2, 0, 4] //Unsorted Array. [7, 5, 9, 3] [6, 2, 0, 4] //An array of 8 items is divided into two arrays of size 4. [7, 5] [9, 3] [6, 2] [0, 4] //Those two arrays divided into halves. [7] [5] [9] [3] [6] [2] [0] [4] //We further, divide those arrays and we achieve atomic value which can no more be divided. [5, 7] [3, 9] [2, 6] [0, 4] //Combine them in exactly the same manner as they were broken down. Then compare the element for each array and then combine them into another array in a sorted manner. [3, 5, 7, 9] [0, 2, 4, 6] //compare above sorted arrays and combine them in a sorted manner. [0, 2, 3, 4, 5, 6, 7, 9] //Merging two sorted arrays into one sorted array.
Merging
> Merging two or more sorted files into a third sorted file is known as merging.
> Three counters, I, J, and K, which are originally set at the beginning of each array, are required by the basic merge algorithm along with two input arrays, A and B, and an output array, C.
> The appropriated counters are advanced and the smaller of A[Actr], B[Bctr], is copied to the following item in C. The remainder of the other array is copied to C once either input array is exhausted.
Merge Sort Algorithm
mergeSort(Array A[0…n]){
if(n==1){
return A;
}
subArray1 = A[0]…A[n/2];
subArray2 = A[(n/2 )+1]…A[n];
subArray1 = mergeSort(subArray1);
subArray2 = mergeSort(subArray2);
return merge(subArray1, subArray2);
}
//An and Bn are the maximum number of elements of array A and B.
merge(Array A, Array B){
Array C;
Actr = 0;
Bctr = 0;
Cctr = 0;
While (Actr<=An-1) and (Bctr<= Bn-1){
if A[Actr] < B[Bctr] {
C[Cctr]=A[Actr]
Actr++;
}
else{
C[Cctr]=B[Bctr]
Bctr++;
}
Cctr++;
}
//Copy remaining elements from A
While (Actr < An-1){
C[Cctr]=A[Actr];
Actr++;
Cctr++;
}
//Copy remaining elements from B
While (Bctr<= Bn-1){
C[Cctr]= B[Bctr];
Bctr++;
Cctr++;
}
return C;
}Merge Sort worst-case time complexity being Ο (n log n)