Merge Sort and Quicksort
This post is part of a series.
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 asis).
merge_sort(array):
if the array is empty or has 1 item:
return the array asis
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 oddlength 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 averagecase 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.
This post is part of a series.