Let’s see what we are getting into.
Some of the classics:
Here is a comparison of nine different algorithms, run against each other, for different distributions:
Here’s a good video with visualizations of 79 algorithms:
I wrote an interactive app for experimenting (see it on CodeSandbox):
Here are a number of common classifications:
Gnome
Bubble
Cocktail
Comb
Odd-Even
Quick
Select
Heap
Smooth
Tournament
Cycle
Cartesian Tree
Insert
Shell
Tree
Splay
Library
Patience
Merge
In-place Merge
Cascade Merge
Oscillating Merge
Polyphase Merge
Bucket
Counting
Radix
Gravity
American Flag
Pigeonhole
Burst
Flash
Bitonic
Pairwise Network
Sample
Block-Merge
Tim
Intro
Spread
Merge-Insert
Grail
Weave
Topological
Pancake
Spaghetti
The Exchange, Selection, Insertion, and Merge groups are part of a larger group of Comparison-Based sorting algorithms, which all sort (in part) by comparing elements against each other and moving them around accordingly.
We can also classify by performance. Roughly speaking, we have:
A single algorithm can be in more than one group; for example, Bogo Sort is an impractical, exchanged-based, comparison sort.
Here are some characteristics of various sorting algorithms, adapted (er, taken) from the excellent Wikipedia page on sorting. ($n$ = number of items to sort, $k$ = number of distinct keys.)
Algorithm | Stable? | Time | Extra Space | Mechanism |
---|---|---|---|---|
Selection Sort | No | $\Theta(n^2)$ | - | Selection |
Insertion Sort | Yes | $\Theta(n^2)$ | - | Insertion |
Bubble Sort | Yes | $\Theta(n^2)$, Best=$\Theta(n)$ in optimized variation | - | Exchange |
Cocktail sort | Yes | $\Theta(n^2)$, Best=$\Theta(n)$ in optimized variation | - | Exchange |
Gnome Sort | Yes | $\Theta(n^2)$ | - | Exchange |
Shell sort | No | Several variants: from slightly worse than $\Theta(n \log n)$ to $\Theta(n^{1.5})$ | - | Insertion |
Comb Sort | No | $\Theta(n \log n)$ | - | Exchange |
Tree Sort | Yes | $\Theta(n \log n)$ | $\Theta(n)$ | Insertion |
Merge Sort | Yes | $\Theta(n \log n)$ | $\Theta(n)$ | Merge |
Quick Sort | No | $\Theta(n \log n)$, Worst=$\Theta(n^2)$ | $\Theta(\log n)$ | Exchange |
Heap Sort | No | $\Theta(n \log n)$ | - | Selection |
Smooth sort | No | $\Theta(n \log n)$ | - | Selection |
Intro Sort | No | $\Theta(n \log n)$ | - | Hybrid |
Tim Sort | Yes | $\Theta(n \log n)$ | $\Theta(n)$ | Hybrid |
Counting Sort | Yes | $\Theta(n+k)$ | $\Theta(n+k)$ | Distribution |
Radix Sort | Yes | $\Theta(ns)$ where s=key length | $\Theta(n)$ | Distribution |
Stooge Sort | Yes | $\Theta(n^{2.71})$ | - | Impractical |
Bogo Sort | No | Expected: $O(n \cdot n!)$, Best=$O(n)$ | $\Theta(n)$ | Impractical |
StabilityA sorting algorithm is said to be stable if it preserves the relative order of equal elements.
Even though programmers will be able to use the sorting routines from a library, you still need to study sorting algorithms and implement some yourself because:
These are too slow to use in practice, but are a great set of algorithms to study! They tend to be simple to describe, and in many cases are the building blocks of the more sophistication ones. Do not skip your study of these classics!
First, find the smallest element and swap it with the first. Then, sort the rest of the list the same way.
function selectionSort(a) { for (let i = 0; i < a.length - 1; i++) { let small = i; for (let j = i + 1; j < a.length; j++) { if (a[j] < a[small]) small = j; } [a[i], a[small]] = [a[small], a[i]]; } }
Sample trace:
20 54 16 36 99 11 74 88 11 54 16 36 99 20 74 88 11 16 54 36 99 20 74 88 11 16 20 36 99 54 74 88 11 16 20 36 54 99 74 88 11 16 20 36 54 99 74 88 11 16 20 36 54 74 99 88 11 16 20 36 54 74 88 99
Notes:
For the 2nd, 3rd, 4th, etc. element: slide backwards into proper relative sorted position.
function insertionSort(a) { for (let i = 1; i < a.length; i++) { let current = a[i]; let j = i; for (; j > 0 && current < a[j - 1]; j--) { a[j] = a[j - 1]; } a[j] = current; } }
Sample trace:
20 54 16 36 99 11 74 88 20 54 16 36 99 11 74 88 16 20 54 36 99 11 74 88 16 20 36 54 99 11 74 88 16 20 36 54 99 11 74 88 11 16 20 36 54 99 74 88 11 16 20 36 54 74 99 88 11 16 20 36 54 74 88 99
Notes:
Systematically examine all pairs of adjacent elements, swapping them when they are out of order. Directly implementing this scheme gives truly awful performance:
function bubbleSort(a) { for (let i = a.length - 1; i > 0; i--) { for (let j = 0; j < i; j++) { if (a[j] > a[j + 1]) [a[j], a[j + 1]] = [a[j + 1], a[j]]; } } }
Ugh, that examines every pair of elements. We need to stop when we make a pass that doesn’t swap anything. This leads to what is sometimes called optimized bubble sort:
function optimizedBubbleSort(a) { let changed = false; for (let i = a.length - 1; i > 0; i--) { for (let j = 0; j < i; j++) { if (a[j] > a[j + 1]) { [a[j], a[j + 1]] = [a[j + 1], a[j]]; changed = true; } } } if (!changed) return; }
Notes:
This is a bidirectional bubble sort. Also called Shaker Sort or Shuttle Sort.
Sorting the way a garden gnome sorts a row of flower pots:
[The gnome] looks at the flower pot next to him and the previous one; if they are in the right order he steps one pot forward, otherwise, he swaps them and steps one pot backward.If there is no previous pot, he steps forwards; if there is no pot next to him, he is done.
The algorithm is pretty nice as there is no “inner loop:”
function gnomeSort(a) { for (let i = 0; i < a.length; ) { if (i === 0 || a[i - 1] <= a[i]) { i++; } else { [a[i], a[i - 1]] = [a[i - 1], a[i]]; i--; } } }
Interesting tweaks can be made to some of the $n^2$ algorithms yielding interesting algorithms whose complexities are somewhere in between $\Theta(n^2) and $\Theta(n \log n)$.
Multiple-pass insertion-sort variant in which items are sifted more than one location at a time at first. The intervals decrease at each pass until they finally get down to one. At one, we do a regular insertion sort, but by this time we are nearly sorted so the insertion sort pass will be pretty fast.
Read Sedgewick’s short paper on the complexity of Shellsort.
Multiple-pass bubble-sort variant where the exchanged items are more than one location away from each other first. The intervals decrease at each pass until they finally get down to one. At one, we do a regular optimized bubble sort, but by this time we are nearly sorted so it won’t be very bad.
Any sorting algorithm that works by comparing elements with each other in order to find the right places for all of them has a lower bound of $\Omega(n \log n)$. These algorithms hit this bound in their average case.
For each item in the array, add it to a binary search tree. Traverse the tree inorder, writing each item back into the array. This is $O(n \log n)$ if you use a balanced or near-balance tree implementation, but can be $O(n^2)$ for degenerate trees.
for x in a: insert x into binary search tree T refill a by traversing T inorder
Note that the space complexity is $\Theta(n)$, which may be too much in some scenarios.
Partition the array so one of the elements is in its final position with smaller elements to its left and larger ones to its right, then (recursively) sort each side.
Notes:
First rearrange the array into a heap by sifting down the non-leaf elements in reverse order. Next, for each element starting at the end and working backwards, swap the element with the top element and sift it down. This builds the sorted array from largest to smallest.
function heapSort(a) { function sift(start, end) { for (let j = start; j * 2 + 1 < end; ) { let k = j * 2 + 1; if (k + 1 < end && a[k] < a[k + 1]) k++; if (a[j] >= a[k]) break; [a[j], a[k]] = [a[k], a[j]]; j = k; } } for (let i = Math.floor(a.length / 2) - 1; i >= 0; i--) { sift(i, a.length); } for (let i = a.length - 1; i >= 0; i--) { [a[0], a[i]] = [a[i], a[0]]; sift(0, i); } }
Recursively: split the list in half, sort each half, then merge the sorted halves together.
Sample trace:
20 54 16 36 99 11 74 88 20 54 16 36 11 99 74 88 16 20 36 54 11 74 88 99 11 16 20 36 54 74 88 99
The direct implementation uses an auxiliary array. So you:
function mergeSort(a, lo, hi, scratch) { if (lo >= hi) return; let mid = Math.floor((lo + hi) / 2); mergeSort(a, lo, mid, scratch); mergeSort(a, mid + 1, hi, scratch); for (let i = lo, j = mid + 1, k = lo; k <= hi; k++) { if (i <= mid && (j > hi || a[i] < a[j])) scratch[k] = a[i++]; else scratch[k] = a[j++]; } for (let k = lo; k <= hi; k++) a[k] = scratch[k]; }
Notes:
A hybrid algorithm! It starts off as quicksort, switches to heapsort when the recursion depth reaches some threshold, then to insertion sort when the number of elements in the range is under another threshold.
Because of this design, it does not suffer from quicksort’s susceptibility to bad behavior. The worst-case complexity for Introsort is $\Theta(n \log n)$. It is used in the standard C++ library’s implementation of std::sort
.
Another hybrid app, based on Mergesort and others. Used in the standard libraries of Python and other languages. It is a stable sort.
Details at Wikipedia.
Partition the items into buckets. Sort each bucket. Read items out of buckets into final array.
There are so many variations of this one, based on how many buckets you choose and what algorithms you use to sort the buckets. We won’t go into detail here.
An algorithm that works really well but only when the items to be sorted have fairly small integer keys. Set up a frequency array whose indices are the range of the values you have to sort. Fill it with zeros. Go through the array you want to sort, incrementing the frequency array incrementing the count for each item you see. Then you can read out the sorted array from the frequencies.
function countingSort(a) { let counts = Array(Math.max(...a) + 1).fill(0); for (let i = 0; i < a.length; i++) counts[a[i]]++; for (let i = 0, j = 0; j < counts.length; j++) { for (let k = 0; k < counts[j]; k++) a[i++] = j; } }
This one only works when the items can be expressed as strings of bits, digits, characters, whatever — and these symbols are ordered. The algorithm is to repeatedly place in buckets (labeled with the symbols) from the least significant symbol to the most significant.
Example with decimal integers:
Input sequence is 759, 43, 989, 6, 206, 855, 209, 903, 102, 199, 721, 188, 5. First place in buckets on least significant digit.
0: 1: 721 2: 102 3: 043,903 4: 5: 855,005 6: 006,206 7: 8: 188 9: 759,989,209,199
The go through the buckets in order, writing into buckets based on the second digit
0: 102,903,005,006,206,209 1: 2: 721 3: 4: 043 5: 855,759 6: 7: 8: 188,989, 9: 199
The go through the buckets in order, writing into buckets based on the first digit
0: 005,006,043 1: 102,188,199 2: 206,209 3: 4: 5: 6: 7: 721,759 8: 855 9: 903,989
Now just read them out in order. Note that this is easy for binary numbers and strings, too. Here’s an implementation assuming the array holds 32-bit integers only:
function* radixSort(a) { // Assumes all values are less than 2**32 const max = Math.max(...a); const radix = 8; // replace this with your desired radix for (let divisor = 1; divisor < 2 ** 32; divisor *= radix) { if (divisor > max) return; let bins = []; for (let i = 0; i < a.length; i++) { let bin = Math.floor(a[i] / divisor) % radix; (bins[bin] ??= []).push(a[i]); } for (let i = 0, j = 0; i < bins.length; i++) { if (!bins[i]) continue; for (let item of bins[i]) a[j++] = item; } } }
These are meant to be bad, and in some cases really, really, really bad. (Most of the following descriptions come from Wikipedia’s Bogosort page.)
This one is purposely silly: recursively sort the first 2/3 of the list, then the last 2/3 of the list, then the first 2/3 again. This gives a $n^{\log 3\,/\,\log 1.5} \approx n^{2.71}$ run time. Sure, we would never really use this in practice, but as far as impracticality goes, it’s nowhere near what is to come. It’s polynomial time, after all.
An algorithm designed, for kicks, to have non-polynomial complexity. Yay! We are starting to get somewhere in our journey of bad algorithms. Here’s how it works:
function slowSort(a, lo, hi) { if (lo >= hi) return; const mid = Math.floor((lo + hi) / 2); slowSort(a, lo, mid); slowSort(a, mid + 1, hi); if (a[hi] < a[mid]) [a[hi], a[mid]] = [a[mid], a[hi]]; slowSort(a, lo, hi - 1); }
Wikipedia says the lower-bound time complexity is $\Omega(n^{\frac{\log n}{2+\epsilon}})$
Repeatedly generate permutations of the array until it is sorted. The permutations can be generated randomly or systematically. Average time complexity is $\Theta((n+1)!)$. Best case is $\Theta(n)$ if your first permutation happens to be sorted, in which case you only need to check that the array is sorted.
function bogoSort(a) { function sorted(a) { return a.every((x, i, a) => !i || x >= a[i - 1]); } function shuffle(a) { for (let i = a.length - 1; i > 0; i--) { const j = Math.floor(Math.random() * (i + 1)); [a[i], a[j]] = [a[j], a[i]]; } } while (!sorted(a)) shuffle(a); }
If the array is already sorted, you are done. If not, swap two random elements and repeat.
Bad Sort is a family of sorting algorithms. For any list $a$, we have $\mathtt{badsort}(k,a)$ for $k \geq 0$, defined as follows:
How bad can this be?
Let’s see what happens with a list $a$ of length 3, that is, $n=3$.
Someone figured out a lower bound for this thing. For $\mathtt{badsort}(k)$, it is in $\Omega((\mathtt{fact}^k(n))^2)$. You can probably see why, as the squared term comes from the complexity of $\mathtt{badsort}(0)$.
Worst Sort is also a family of algorithms. For any list $a$, we have $\mathtt{worstsort}(f,a)$ for any $f: \mathbb{N} \rightarrow \mathbb{N}$ of your choosing, defined as:
$\mathtt{worstsort}(f,a) = \mathtt{badsort(f(a.\mathtt{length}), a)}$
Choose $f$ to be arbitrarily bad. As long as it terminates.
To really get a sense of what’s going on here, see Brent’s article on Worstsort.
Keep checking the array until it is sorted, hoping that changes occur via supernatural intervention or changes in memory state due to ionizing particles or other radiation.
Which algorithm (or combination of algorithms!) is right for you depends on your particular application. Ask yourself:
Congratulate yourself for getting this far. Now you are allowed to use the built-in sorting operations that your language provides for you.
Java has different methods for performing in-place mutable sorts on arrays versus collections (such as lists). It has:
Arrays.sort(a)
Arrays.sort(a, comparator)
Collections.sort(c)
Collections.sort(c, comparator)
For non-in-place sorts, you need to use streams, for example:
stream.sorted()
stream.sorted(comparator)
So what’s a comparator? Basically it’s a function that takes two values and returns -1 if the first is less than the second, 0 if the two are supposed to compare equal, and 1 if the second is larger than the first. Note you can only use the version without comparators if the values being compared are of a type with a natural order.
import java.math.BigDecimal; import java.util.Arrays; import java.util.Collections; import java.util.List; import java.util.ArrayList; import java.time.LocalDate; public class BuiltInSortingDemo { record Employee(String name, LocalDate birthday, BigDecimal salary) { } public static void main(String[] args) { // Sort a simple array var numbers = new int[] { 9, 3, 8, 9, 2, 1 }; Arrays.sort(numbers); System.out.println(Arrays.toString(numbers)); // Sort a simple list var moreNumbers = new ArrayList<Integer>(List.of(9, 3, 8, 9, 2, 1)); Collections.sort(moreNumbers); System.out.println(moreNumbers); var employees = new Employee[] { new Employee( "alice", LocalDate.of(1999, 1, 1), BigDecimal.valueOf(1875.00)), new Employee( "bella", LocalDate.of(1988, 1, 1), BigDecimal.valueOf(2000.00)) }; // Sort by increasing name Arrays.sort(employees, (e1, e2) -> e1.name.compareTo(e2.name)); System.out.println(Arrays.toString(employees)); // Sort by decreasing salary Arrays.sort(employees, (e1, e2) -> e2.salary.compareTo(e1.salary)); System.out.println(Arrays.toString(employees)); // We can also sort lists of employees var list = Arrays.asList(employees); Collections.sort(list, (e1, e2) -> e1.name.compareTo(e2.name)); System.out.println(list); // Here we sort in a stream, so it is not in-place but rather a new one System.out.println(Arrays.toString( list.stream() .sorted((e1, e2) -> e2.salary.compareTo(e1.salary)) .toArray())); System.out.println("Everything that could be sorted got sorted"); } }
TODO
TODO
TODO
We’ve covered: