Merge Sort

Merge sort algorithm another divide and conquer algorithm which is also not in-place and that is where its similarity with Quicksort algorithm ends.  Merge sort running time is always O(n log n) regardless of the order of data which gives merge sort an edge over quicksort where data order does not influence cost in time. This algorithm is useful when you want to sort data where knowing every time before hand how long it will take to sort n amount of data is important. Like quicksort, a mergesort algorithm can also be modified to be in-place however the code I will provide does not cover this method.
Merge sort works by first dividing the array into two. The two sides are further divided and this division continues until no further divisions are possible. Each respective divided portions are then merged(in ascending order). To see how this process works lets take an arbitrary set of data of size n. After several division steps we have a set of divided arrays on the left side of the first split and a set of similar description on the right. Since the process of splitting and merging is exactly the same, we only need to look at a small proportion to see how it works. Lets take a set that is so far down the split, at a depth h,  that there are now only 4 elements left in the array on the left side of the original divide.

Array: 2 9 3 1
Split further
2 9      31
Split further
2        9                3        1
Can't split any further as each split has only one element.
Now we call the "Merge" algorithm to merge the elements in the right order.
We create a new array of the size of the total of two elements to be merged hence of size 2.
Merge:
2 < 9 = true. 2 goes to first element of empty array.
No more elements left in first array, rest of second array which is in theory already in its sorted form is copied to the new array hence final look of new array:
Array: 2 9
We do the same with the right side.
3 < 1 = false.
Store 1 into first element of new array. Whats left is 3 so copy that into the last cell of the new array.
New array  now looks like:
Array: 1 3
Now we have two sorted arrays [2, 9] and [1, 3] to merge.
Same process takes place.
new array = [,,,];
2 < 1 = false.
new array[1,,,]
2 < 3 = true
new array[1,2,,]
9 < 3 = false.
new array[1, 2, 3,]
Whats left is 9 hence new array[1, 2, 3, 9]
In the next merge attempt array [1, 2, 3, 9] will be merged with another array of same or similar length using the exact same method. Hence this can be achieved through a recursive algorithm.

We can see that in regards to coding this we will need three methods. A MergeSort method which wraps the MergeSort Algorithm. A RecursiveMergeSort which Performs a recursive dividing of the array down to one element array. Lastly we will need a Merge algorithm which will take two arrays to be merged. In our code we use two arrays the same size of the original array before division, and then use indices to "simulate" creating arrays at each merge. This reduces the arrays we need per division from three, to two. Merge then applies a merging algorithm so that the final result of the merge is a sorted array of the given elements.

The Code:
MergeSort method:

public void MergeSort(ref int[] array)
{
  int[] buffer = new int[array.Length];
  RecursiveMergeSort(ref array, ref buffer, 0, array.Length-1);
}

The above code works simply by creating a new array, 'buffer', the same length as the original 'array'. These two arrays are then passed to the RecursiveMergeSort method with the orignal array as first parameter. The start length, which almost always will be zero in this method, is sent along with the zero indexed length of the array.

RecursiveMergeSort method:

private void RecursiveMergeSort(ref int[] sequence, ref int[] buffer, int start, int end)
{
  int n = (end - start) + 1;
  if (n < 2) return;
  int m = start + (n / 2);
 
//Copy values from original array into buffer which will be the left side of the divide.
  for (int i = start; i < m; i++)
    buffer[i] = sequence[i];
 
 //Left side divide
  RecursiveMergeSort(ref buffer, ref sequence, start, m - 1);
 //Right side divide.
  RecursiveMergeSort(ref sequence, ref buffer, m, end);
 //Merge
  Merge(ref sequence, ref buffer, start, end, m);
}

The RecursiveMergeSort method is the divide portion of the algorithm which calls Merge at the end. As this is the recursive algorithm, by the time merge is called, the respective left and right partitions which were called recursively has returned with sorted data in each partition to be merged. It gets the size of the hypothetical n (which shrinks clearly deeper into the divide recursion), hence hypothetical size. The code then checks if there is only a one element array present. Returns if this is the case since a single element is already considered sorted. For an array with more than one element, it finds the midpoint m to divide the array at. The set of data between the appropriate start and end marks in the original array, sequence, are respectively copied to the second array, buffer. The division then commences with a recursive call that passes for the left array the copied array as first and the original array as the second array along with the start of the array and a point one less than mid point. Similarly for the right side the original array is passed as first, followed by the second array, then the mid point m as the new start position and the end point end as the new end point of the array. Merge is called once the recursive operations return.

Merge method:

private void Merge(ref int[] sequence, ref int[] Left, int start, int end, int m)
{
  int i = start;
  int j = m;
  int index = start;
  while(i < m && j <= end)
  {
    if (Left[i] > sequence[j])
      sequence[index++] = sequence[j++];
    else
      sequence[index++] = Left[i++];
   }
 
 //Order is important here. Since our left side is in Left array, 
  //this should have the smallest value so we copy this first.
  //Left side might have something left over
  while(i < m)
  {
    sequence[index++] = Left[i++];
  }
  //Right side might have something left over.
  while (j <= end)
  {
    sequence[index++] = sequence[j++];
  }
} 

The Merge method is the more complicated of the three methods.  Index i and j are used as indices and are set respectively as start position of the passed array, the end point of the passed array, and the midpoint m of the array which acts as the end point of the first array. The first while loop does the merging of the two arrays by using the elements of the first array, sequence, as test against the second array, Left, to determine which of the two elements gets placed in the conjoined array. The second two while loop will copy the remainder, theoretically sorted, data into the conjoined array. The cycle repeats as each recursive call returns in the earlier RecursiveMergeSort method.

The running time for Merge sort is O(n log n) and this is maintained regardless of the sorted condition of the array. In choosing between Quicksort and Mergesort the first question you will need to ask is, what will be the sorted condition of the data in a  majority of cases? Bear in mind that sorted data in Quicksort, if we assume no improvement modifications to the algorithm, will draw a quadratic time cost.

Next: HeapSort.
Previous: Quicksort.
Landing page: Part One.