So far in this series on sorting algorithms,
we have talked about 3 of the sorting algorithms – selection sort, bubble sort and
insertion sort. And we have seen that these algorithms are not so fast, they’re all O
(n^2) in average case. Now in this lesson, we’re going to talk about one algorithm which
is O(nlogn) in worst case and this algorithm is Merge Sort, O(nlogn) in worst case is definitely
a lot better, a lot faster than O(n^2) in average case. So, in this lesson, we will
study, discuss and analyze Merge Sort Algorithm. There’s one pre-requisite for this lesson.
You should have at least heard about recursion as a programming concept. Ok, so let’s get
started. Once again, I will pick up a very simple sorting scenario. Given a list of integers
in a form of an array, something like this. Let’s name this array A. We have 8 elements
in the array. So, we have indices from 0 to 7. We want to sort this list in increasing
order of value of integers, so the list should be rearranged like this. Our approach in Merge
Sort Algorithm will be entirely different from what we’ve done in previous sorting algorithms,
where we’re rearranging the elements or changing their positions only by swapping or shifting.
What we’re going to do here is we’re going to break this problem into sub problems. We
will divide this array into two equal halves, or rather two possibly equal halves. So, we
will find some middle position and we can say that all the elements before this position
belong to the first half and all the elements after, on or after this position belong to
the second half. If an array would’ve odd number of elements, one of the halves will
have more elements than the other half. We’ve 8 elements in the original array here. So
we’ve two equal halves. Now think about this, what if we are somehow able to sort these
two halves, and let’s say these two halves are entirely different arrays. They are created
separately in memory by copying values from the original array A. If we’re somehow able
to sort these two arrays, then we can merge these two lists together in original list
in sorted order. Of course, there has to be some algorithm to merge two sorted arrays
into a third array in sorted order. The algorithm will be pretty straightforward, let’s say
this particular sub array is named L and this particular sub array is named R; L for Left
and R for Right. Because all the elements in A are present either in L or R, we can
start overwriting A from left to right. We can start at 0th position in A. At any point,
the smallest element will be either the smallest ‘unpicked’ in L, or the smallest ‘unpicked’
in R, and let’s say we colour code the smallest ‘unpicked’ in L and R by this yellow colour.
What we can do is we can pick the smaller of the two smallest ‘unpicked in L and R.
We’ve two candidates here – 1 and 3. 1 is smaller, so we can write 1 here at 0th index.
And now we can look for the number to fill at 1th index in A. Let’s say, the cells of
the ‘picked’ elements will be colour coded in green. If I have to write ‘pseudo-code’
to merge the elements of the two sorted arrays into a third array, let’s say we want to write
a function named ‘Merge’ that will take three arrays as arguments – Left(L), Right(R) and
the array(A) in which it should be merging two sorted arrays- Left(L) and Right(R). Then,
I will do something like this; I will take the variable that will store the number of
elements in L, and another variable that will store the number of elements in R. In a real
program, we can also pass these two values to the function. Now, I will take three variables
— I, j and k; and initialize them all to 0. Let’s say, I will mark the index of the
smallest ‘unpicked’ in L, ‘j’ will mark the index of the smallest unpicked in R and k
will mark the index of the position that needs to be filled in A for our example here at
the stage of i=1, j=0 and k=1; because we’ve already filled one element at index 0 in A.
But when we will start, we will start with all three i, j and k as 0. And now, my code
will go like, while i