Merge Sort vs Quick Sort

In the following article, I will be doing a simple analysis of Merge Sort vs Quick Sort, two of the most efficient comparison-based sorting algorithms. This article assumes knowledge of the usage of arrays (in C++).

Merge Sort

Merge Sort in a nutshell

While Merge Sort is widely known as the divide-and-conquer algorithm, it can be further described as a “break it down and then merge it back up (in the correct order)” algorithm. In order to break the array down to its basic component, which is an array of one number, the algorithm continuously splits the array into half. This process repeats until there is only one element left in each array, and by default, that element will be sorted (trivially). After that, the algorithm seeks to merge each of the smaller sized array into a larger one, in the correct order, until the original array is merged completely, in sorted order. And that is really it for Merge Sort. I have created a diagram to better illustrate this.

Merging in order

Imagine you are a primary school teacher, and you have 4 girls and 4 boys arranged in ascending order based on height. How will you then arrange all 8 of them together such that they are still in ascending order? By making use of the fact that they were already arranged previously, of course! You would compare girl-1 and boy-1, and if girl-1 was shorter, she would stand in the “sorted” line first, and then you would compare girl-2 and boy-1. Repeating this process, either boy-4 or girl-4 will be the last in the “sorted” line, and the other would still be “unsorted” (ie not in line). By then, you can make the assertion that whoever is not in the “sorted” line is the tallest, and you can just line them at the back.

void merge(int* arr, int low, int mid, int high) {
  int N = high-low+1; 
  int b[N]; // auxillary array
  int left = low, right = mid+1, bIndex = 0;
  // Assertion: low to mid is sorted, mid+1 to high is sort
  while (left <= mid && right <= high) 
    b[bIndex++] = (a[left] <= a[right]) ? a[left++] : a[right++];
  
  while (left <= mid) 
    b[bIndex++] = a[left++]; // Either this triggers...
  while (right <= high) 
    b[bIndex++] = a[right++]; // ... Or this
  
  for (int k = 0; k < N; k++)
    arr[low+k] = b[k]; // Copying the array back to its original place
}

Recursive vs Iterative Merge Sort

Merge Sort can be performed using loops iteratively, or recursively. There is no difference between the time complexity or space complexity, but the way each method deals with leftover elements is interesting. As mentioned previously, Merge Sort works by repeatedly cutting each array into half, but in the case where the number of elements is not 2^n, the cutting process would cause leftover elements. Let us take a look at how each algorithm is coded.

Recursive Merge Sort (Recommended)

void RMergeSort(int* arr, int low, int high) {
  if (low < high) {
    // <i>Base case low >= high implying 0 or 1 item</i>
    int mid = (low+high)/2;
    RMergeSort(arr, low, mid);
    RMergeSort(arr, mid+1, high);
    merge(arr, low, mid, high);
  }
}

Iterative Merge Sort

void IMergeSort(int* arr, int size) {
  int p, l, h, mid, i;
  for (p = 2; p <= size; p*=2) {
    for (i = 0; i+p-1 < size; i+=p) {
      l = i;
      h = i + p - 1;
      mid = (l+h)/2;
      merge(arr, l, mid, h);
    }
  }
  if (p/2 < n) // <i>Implying leftover elements</i>
    merge(arr, 0, p/2, n-1);
}

In the recursive Merge Sort, this is how “odd” elements (not 2^n) will be treated in the recursive call. We can also see that the code for recursive Merge Sort is quite a bit shorter than the iterative version, hence, recursion is the way to go!
Additionally, note that in the code, merging is done last. This will ensure that index low to mid, and (mid+1) to high will already be sorted, before merging is done.

Quick Sort

A quick glance @ Quick Sort

Previously, you played the role of the teacher in Merge Sort. In Quick Sort, you will play the role of the student. Imagine your teacher has tasked the class to line up in ascending order based on height. In order to find your place, you look for a spot where everyone in front of you is shorter than you, and everyone behind you is taller than you. This way, you will definitely be in the right spot, and you will then place all your trust in your classmates that they do the same. The idea of Quick Sort is analagous to this! An element is sorted if and only if all elements before are smaller, and all after are bigger. When every element follows this idea, every element will be in the right place, and the list will be sorted.

Quick Sort Analysis

The general idea of Quick Sort is, let the first element of the array be the pivot, holding the value which we will call “key”. Having two pointers (called left and right) at the start and end of the array, repeatedly check if the left element is greater than the key, and if the right element is smaller than the key. When each are found, swap their positions. This is similar to how the element ensures all elements smaller than it, are actually before it and not after it, and vice versa. Once the whole array is configured (aka swapped to perfection), slot the pivot in. This “partitioning process” can now be done for elements before and after the pivot. By recursively doing this, we can ensure that every element will become the pivot, and be in the right place, thus sorting the list.

Quick Sort Depiction and Code

// Partitioning to find PIVOT's index
int partition(int* arr, int low, int high) {
  int key = arr[low];
  int l = low, h = high;
  while (l < h) {
    while (arr[l] <= key) { l++; }
    while (arr[h] > key) { h--; }
    if (l < h)
      swap(arr[l], arr[h]);
  }
  // Swap the pivot into its place
  swap(arr[low], arr[h]);
  return h;
}

void QuickSort(int* arr, int l, int h) {
  int pivot;
  if (l < h) {
    pivot = partition(arr, l, h);
    // Since pivot is already in correct place...
    QuickSort(arr, l, pivot-1);
    QuickSort(arr, pivot+1, h);
  }
}

Table Of Summary

Conclusion

As we can see, right now, Quick Sort is not as efficient (time complexity wise) as compared to Merge Sort. However, Merge Sort is pretty much just like that, while many improvements can be made to Quick Sort. In the near future, I will be trying out and uploading ideas/code to optimise QuickSort. These include pivoting the correct way using probability analysis, planning for duplicates, and possibly integrating Insertion Sort (another type of sort) that can reduce recursion overhead in Quick Sort. Also, ideas to explore are Multi-pivot Quick Sort (studies have shown that having 5 pivots can increase the speed of Quick Sort), and planning for duplicates.

Return to Posts