Merge Sort and Quicksort

by Justin Skycak on February 07, 2021

Merge sort and quicksort are generally faster than selection, bubble, and insertion sort. And unlike counting sort, they are not susceptible to blowup in the amount of memory required.

This post is a chapter in the book Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents. Suggested citation: Skycak, J. (2021). Merge Sort and Quicksort. Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents. https://justinmath.com/merge-sort-and-quicksort/

Merge sort is a sorting algorithm that works by breaking an array in half, recursively calling merge sort on each half separately, and then merging the two sorted halves. The base case is that empty arrays and arrays of 1 item are already sorted (so if you call merge sort on such an array, it leaves the array as-is).


merge_sort(array):
    if the array is empty or has 1 item:
        return the array as-is

    otherwise:
        break the array in half
        recursively call merge_sort on each half separately
        merge the two halves and return the result

Note that when an odd-length array is broken in half, it is okay for one of the halves to have one more item than the other half.

Example of Merge Sort

Below is a concrete example illustrating how merge_sort sorts an array.


merge_sort([6,9,7,4,2,1,8,5])
|    halves: [6,9,7,4] [2,1,8,5]
|
|--> merge_sort([6,9,7,4])
     |    halves: [6,9] [7,4]
     |
     |--> merge_sort([6,9])
          |    halves: [6] [9]
          |
          |--> merge_sort([6])
               |
          |<-- [6]
          |
          |--> merge_sort([9])
               |
          |<-- [9]
          |
          merge([6],[9])
     |<-- [6,9]
     |  
     |--> merge_sort([7,4])
          |    halves: [7] [4]
          |
          |--> merge_sort([7])
               |
          |<-- [7]
          |
          |--> merge_sort([4])
               |
          |<-- [4]
          |
          merge([7],[4])
     |<-- [4,7]
     |
     merge([6,9],[4,7])
|<-- [4,6,7,9]
|
|--> merge_sort([2,1,8,5])
     |    halves: [2,1] [8,5]
     |
     |--> merge_sort([2,1])
          |    halves: [2] [1]
          |
          |--> merge_sort([2])
               |
          |<-- [2]
          |
          |--> merge_sort([1])
               |
          |<-- [1]
          |
          merge([2],[1])
     |<-- [1,2]
     |  
     |--> merge_sort([8,5])
          |    halves: [8] [5]
          |
          |--> merge_sort([8])
               |
          |<-- [8]
          |
          |--> merge_sort([5])
               |
          |<-- [5]
          |
          merge([8],[5])
     |<-- [5,8]
     |
     merge([1,2],[5,8])
|<-- [1,2,5,8]
|
merge([4,6,7,9],[1,2,5,8])
[1,2,4,5,6,7,8,9]

Quicksort

Another sorting algorithm, quicksort, is very similar to merge sort. The only difference is that instead of splitting the array in half, we randomly choose a pivot element and split the array into $3$ pieces: elements that are less than the pivot element, elements that are equal to the pivot element, and elements that are greater than the pivot element. Then, we apply quicksort recursively on the “less than” and “greater than” pieces before combining the pieces.


quicksort([6,9,7,4,2,1,8,5])
|    pivot: 7
|    pieces: [6,4,2,1,5] [7] [9,8]
|
|--> quicksort([6,4,2,1,5])
     |    pivot: 5
     |    pieces: [4,2,1] [5] [6]
     |
     |--> quicksort([4,2,1])
          |    pivot: 2
          |    pieces: [1] [2] [4]
          |
          |--> quicksort([1])
               |
          |<-- [1]
          |
          |--> quicksort([4])
               |
          |<-- [4]
          |
          combine([1],[2],[4])
     |<-- [1,2,4]
     |  
     |--> quicksort([6])
          |
     |<-- [6]
     |
     combine([1,2,4],[5],[6])
|<-- [1,2,4,5,6]
|
|--> quicksort([9,8])
     |    pivot: 9
     |    halves: [8] [9] []
     |
     |--> quicksort([8])
          |
     |<-- [8]
     |  
     |--> quicksort([])
          |
     |<-- []
     |
     combine([8],[9],[])
|<-- [8,9]
|
combine([1,2,4,5,6],[7],[8,9])
[1,2,4,5,6,7,8,9]

Time Complexity

With an average-case time complexity of $O(n \log n),$ merge sort and quicksort are generally faster than selection, bubble, and insertion sort. And unlike counting sort, they are not susceptible to blowup in the amount of memory required.

Exercises

Implement merge sort and quicksort. As always, be sure to write plenty of tests that cover a variety of cases (negative numbers, repeated numbers, duplicates, decimals, etc).

Write a helper function merge(arr1, arr2) that merges two sorted arrays by repeatedly looking at the first element of each array and moving the smaller one into a new array.
Write a function merge_sort(arr) that sorts an array using the merge sort algorithm.
Write a function quicksort(arr) that sorts an array using the quicksort algorithm.