Merge Sort explained

For past few days i have been going back to basics. these are the topics which got me started with coding in the first place. Although these are simple topics in Computer science but form the very basic of coding in any language.

Well lets start off with some back ground about the Merge Sort. This basically comes from the family of algorithms which is based on divide and conquer methodology(If you know your history almost all civilizations at some point of time had someone playing this game in the kingdom).

The intent is to divide a big problem(in this case a array ) into smaller problems so that they can be solved easily(by easily i mean in few lines of code). Imagine if you have a array of 10,000 objects and you want to sort it according to their values (in this case we will take a simple example of a integer generally these are complex objects but the principle remains the same). If we divide this array till it becomes a single element then we simply compare the element and get the result, that forms the basis of this algorithm. We will divide a array till we have two arrays having only one element and then we compare them and merge the arrays.

So, we have two steps

1. Divide till we reach to a point where we have 1 element which can be compared.
2. merge the elements.

For all the math interest groups, these are Mathematical Induction problems where you have a base case (in this case a array with elements which can be compared and merged in one go) and the repeating case.

Merging 

Lets look at Merging two sorted arrays first. We will be doing this when we divide the single array into two and then we will merge it.

Input array A = 11,33,55,77,99

Input array B = 22,44,66,88

For merging these 2 arrays we will choose each element and compare with each other and push in a new array. 

Iteration 1: compare 11 with 22

11 is smaller hence we push it in a new array C and increment the counter for A. 

then we compare next element in A with same element in B i.e. 33 with 22 now 22 is smaller hence we push 22 in C and increment the counter for B.

array C : 11,22

After all the iteration we will have one single array with sorted elements.

Recursion

Now let's look at recursion part of it. Our focus here is to divide the problem into smaller parts till we reach the base case.

e.g. Input Array = 55,33,44,11,22

we will take a lower pointer (0 position ) and upper pointer(4 position) and calculate the mid. Now we will call the same method with upper pointer as mid and same value of lower pointer.

We will keep on calculating till we have lowerPtr == UpperPtr then we have only one element.

Similarly we will call same method again with mid as lower pointer and same value for upper pointer.

The code will look like this.

public void recMergeSort(int[] workspace, int lowerBound, int upperBound) {

if (lowerBound == upperBound) {

return;

} else {

int mid = (lowerBound + upperBound)/2;

recMergeSort(workspace, lowerBound, mid);

recMergeSort(workspace, mid + 1, upperBound);

merge(workspace, lowerBound, mid + 1, upperBound);

}

}

We use workspace array to hold the merged output

the last line submits the array to get it merged, here we will divide the same array in two parts from lower to mid and from mid+1 to upper.

Here is the Java code for it.

public void merge(int[] workspace, int lowPtr, int highPtr,
int upperBound) {
int i = 0; // workspace index
int lowerBound = lowPtr;
int mid = highPtr - 1;
int n = upperBound - lowerBound + 1;  // number of items
while (lowPtr <= mid && highPtr <= upperBound) {
if (array[lowPtr] < array[highPtr]) {
workspace[i++] = array[lowPtr++];
} else {
workspace[i++] = array[highPtr++];
}
}
while(lowPtr <= mid){
workspace[i++] = array[lowPtr++];
}
while(highPtr <= upperBound){
workspace[i++] = array[highPtr++];
}

for (int j = 0; j < n; j++) {
array[lowerBound + j] = workspace[j]; // copy the merged array back
}
}
Since we keep on dividing the array into 2 parts, the final time complexity of this algorithm is O(n log n)
Please keep in mind the base of Log is 2 here.

For better time complexity we compromise on space here as we are using 2 arrays of the same size, so if you are programming on device which is limited on size you might want to consider more complex sorting algorithms but more on that later.


References :
Data Structures & Algorithms in Java by Robert Lafore