Everything you need to know about Merge Sort algorithm
What is merge sort?
Merge Sort is a method of sorting that uses the divide and conquer strategy.
In simpler words, it divides the array that is given into two halves, recursively calls itself for the two halves and then merges the sorted halves.
Why is merge sort important?
Merge sort has a worst-case, average-case and best-case time complexity of O(n log n). This is quasilinear time, which hosts some of the fastest possible comparison sort algorithms including Quicksort and Heapsort.
How does merge sort work?
We can consider an unsorted array shown below:
{ 65 24 31 12 6 2 1 19 }We will now divide the whole array into equal halves. Since the above array has 8 values, then it can be divided into two arrays of 4 values each. (If the size of the array is odd, then don’t worry — the last value will be left aside till the sorting process).
{ 65 24 31 12 } { 6 2 1 19 }We will divide these two arrays into halves again.
{ 65 24 } { 31 12 } { 6 2 } { 1 19 }These arrays will now be divided into halves again, such that they cannot be divided again (carries a single value).
{ 65 } { 24 } { 31 } { 12 } { 6 } { 2 } { 1 } { 19 }Now the values will be combined together in an array the same way it was broken down. To do this, we have to compare the element for each list and then combine them into another list while sorting them. Taking the first two values into consideration, we can see that they are not in the right order, so we will swap their positions before assigning them into one array. This process will continue for the rest of the values accordingly.
{ 24 65 } { 12 31 } { 2 6 } { 1 19 }In the next iteration we will compare the values once again and merge them into two arrays.
{ 12 24 31 65 } { 1 2 6 19 }Then comes the final iteration, which will compare values and merge the two arrays into one.
{ 1 2 6 12 19 24 31 65 }
