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