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.

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]


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]


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.


Practice Problems


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).

  1. 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.
  2. Write a function merge_sort(arr) that sorts an array using the merge sort algorithm.
  3. Write a function quicksort(arr) that sorts an array using the quicksort algorithm.

Leave a Comment