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.

Quicksort

This is one of the divide and conquer algorithm and sometimes hard to work out on paper what is going on. Quicksort algorithm is also not an in-place algorithm because it requires the use of additional memory to process partitioned sub-arrays. However quicksort can be made in-place through some tricks and the algorithm code I will present today will be an in-place algorithm.

The idea of quicksort is simple enough where you chose a pivot and arrange the elements so that each element bigger than the pivot is on its right and smaller is on its left. At this point the pivot in theory is in its final sorted position. We then take all the elements on the left and create a new array and perform the same operation. Similarly we do the same to all the elements on the right of the pivot. Eventually we reach the last element and the array is sorted and we copy them back in their ordered form.

So how does the algorithm work in detail? The first step is to decide how the pivot is chosen. In this example I will simply use the last element in the current partition as the pivot however there are other techniques such as median of three and random. The importance of choosing the pivot will be clear later however because it does make a difference to the worst case running time. Once the pivot is selected we will swap it with the element at the beginning of the array and then we can start testing. We have a left index indexing the beginning of the array but to the element after the pivot. We also have a right index that indexes the last element of the array. After this we first increment the left index and compare each element until it is at an element that is bigger than the pivot. We then start decrementing the right index and comparing each element it is indexing until it reaches an element smaller than the pivot. At this point we swap the elements pointed to by the left and right indices with each other. This step is repeated until the left index is bigger than the right index at which point we know the pivot is in the right place. We then swap the pivot with the element pointed to by the right index. Here is a small scale example with 5 elements.

Array "q"
initial. Pivot = 5 at index 4.
6 3 1 2 5:
5 3 1 2 6: Swapped pivot with first element. Pivot 5 is now at index 0.
left index l = 1, right index r = 4. (Zero index based).
Start:
q[l] > q[pivot]? no. l = 1 + 1 = 2.
q[l] > q[pivot]? no. l = 2 + 1 = 3.
q[l] > q[pivot]? no. l = 3 + 1 = 4
q[l] > q[pivot]? yes, stop.
q[r] > q[pivot]? yes. r = 4 -1 = 3.
left index is bigger than right index, swap q[r] with q[pivot]:
2 3 1 5 6.
Pivot 5 is now in its final position, so now we partition.
Left side                              5                          Right side
2 3 1                                                                    6
Pivot = 1 at index 2.                               One element so
                                                              already sorted.  

"q" = new array.
1 3 2: Swapped pivot with first element. Pivot 1 is now at index 0.
l = 1, r = 2.
Start:
q[l] > q[pivot]? yes, stop.
q[r] > q[pivot]? yes. r = 2 -1 = 1.
q[r] > q[pivot]? yes. r = 1 -1 = 0.
left index is bigger than right index, swap q[r] with q[pivot]:
1 3 2: no change because r = pivot index.
Pivot 1 is now in its final position, so now we partition:
1      Left                  Right           5                     6
         none                 3 2
"q" = new array 3 2.
Pivot = 2 at index 1.
3 2 Swap Pivot with first element. Pivot 2 is now at index 0.
2 3
l = 1, r = 1.
Start.
q[l] > q[pivot]? yes, stop.
q[r] > q[pivot]? yes. r = 1 -1 = 0.
left index is bigger than right index, swap q[r] with q[pivot]:
2 3: no change because r = pivot index.

Pivot 2 is now in its final position so now we partition:
1       2         Left side         Right side      5            6       
                       None                   3
                                          One element so
                                          already sorted.
Final:
1 2 3 5 6

As you can see from the above step-through of a short array it is a lot of work on paper however thankfully the running time is more forgiving. Quicksort average case is O(n log n) and worst case of O(n^2). Worst case running time occurs when the array is either sorted or reverse sorted however we can improve this as mentioned earlier by changing the way we choose the pivot and the way we use the pivot. To develop this into code, a careful analysis indicates we need 5 methods.
QuickSort: Passes an array and initial condition to QuckSortAlgorithm
QuickSortAlgorithm: Performs the QuickSort Division and Partitioning
Partition: Performs the Quicksort operation on the partition.
GetPivot: Returns the pivot position of the chosen pivot and after moving it to front of array.
Swap: Swaps two elements in an array.
Swap method has already been explained on the main page.

The code for the QuickSort method:

public void QuickSort(ref int[] array)
{
  QuickSortAlgorithm(ref array, 0, array.Length - 1);
}

The code for the QuickSortAlgorithm method:

public void QuickSortAlgorithm(ref int[] array, int left, int right)
{
  if (left < right)
  {
     //Partition by finding and returning final pivot position.
     int pivotIndex = Partition(ref array, left, right); 
    QuickSortAlgorithm(ref array, left, pivotIndex - 1);
    QuickSortAlgorithm(ref array, pivotIndex + 1, right);
  }
}

The code for the Partition method:

public int Partition(ref int[] array, int left, int right)
{
  //Pick pivot.
  int pivotIndex = GetPivot(ref array, left++, right);
  int newPivotIndex = pivotIndex;
  while (left <= right)
  {
    while (left <= right && array[left] <= array[pivotIndex]) left++; //move left pointer.
    while (left <= right && array[right] >= array[pivotIndex]) right--; //move right pointer.
    if(left < right) Swap(ref array, left, right); //Swap elements at left and right indices.
  }
  //Swap pivot from current position to final position.
  if (left > right) newPivotIndex = right;
  Swap(ref array, pivotIndex, newPivotIndex);
  return newPivotIndex;
}

The code for the GetPivot method:

private int GetPivot(ref int[] array, int left, int right)
{
  Swap(ref array, left, right);
  return left;
}

From the above code it is quite clear that a lot of work is done in the Partition method.
The explanation of how the above code works is trivial and is explained in the third paragraph above. In the QuickSortAlgorithm method the statement if (left < right) ensures that recursion only runs if there are more than one element. You will also notice why this method is in-place; because the same array is used so no additional memory to store the array is used. In C# this is achieved through passing by reference. This is a good all around algorithm to use and many programming languages built in sorting uses some form of quicksort algorithm.

Next: MergeSort.
Previous: Insertion Sort.
Landing page: Part One.