Algorithm/Insights
Merge sort is a comparison based algorithm that uses divide and conquer approach to sort an array in O(n logn) time.
Merge sort is a stable sort i.e. it preserves the order of same array elements after sorting.
Algorithm for Merge sort is:
Step 1. Divide the array into 2 halves recursively.
Step 2. Merge the divided parts in sorted order.
Here is an example that explains the algorithm:
First, the array {12, 35, 87, 26, 9, 28, 7} is divided to sub arrays {12, 35, 87, 26} and {9, 28, 7} as shown in the image above.
Then {12, 35, 87, 26} is divided into {12, 35} and {87, 26}.
Next {12, 35} is divided into {12} and {35}
At this step, no further division is possible on single element arrays {12} and {35}.
Next step is to merge these arrays in sorted order to get {12, 35}
Next {87, 26} is divided into {87} and {26}
Similar as above, we merge these single element arrays in sorted order to get {26, 87}
Now we are at the step where we have {12, 35} and {26, 87}. We merge these subarrays in sorted order to form sorted array: {12, 26, 35, 87}
Similarly, {9, 28, 7} is also first divided recursively and then merged in sorted order to get sorted array {7, 9, 28}
Finally, we merge sorted subarrays {12, 26, 35, 87} and {7, 9, 28} in sorted order to get the sorted array {7, 9, 12, 26, 28, 35, 87}.
Here is the algorithm for merging 2 sorted arrays used by merge sort algorithm given in the code snippet section:
1. Create temporary arrays temp1 and temp2.
2. Copy elements of first subarray to temp1. So, temp1 = {12, 26, 35, 87}
3. Copy elements of second subarray to temp2. So, temp2 = {7, 9, 28}
4. Now copy elements from temp1 and temp2 to the original array in sorted order:
a. Traverse arrays temp1 and temp2 together:
b. If temp1[i] <= temp2[j], then copy temp1[i] to the original array and move i to next element in temp1.
c. Else copy temp2[j] to the original array and move j to next element in temp2.
d. If end of one temporary array is reached, then copy the elements of the other temporary array to the original array in the same order.