Sorting

We sort to make it easier to find things. Also because sometimes things look good when sorted. Yep, things all tidied up, all in order.

Demos First

Let’s see what we are getting into.

Videos

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:

An Interactive Demo

I wrote an interactive app for experimenting (see it on CodeSandbox):

Classification of Algorithms

Here are a number of common classifications:

Exchange

Gnome
Bubble
Cocktail
Comb
Odd-Even
Quick

Selection

Select
Heap
Smooth
Tournament
Cycle
Cartesian Tree

Insertion

Insert
Shell
Tree
Splay
Library
Patience

Merge

Merge
In-place Merge
Cascade Merge
Oscillating Merge
Polyphase Merge

Distribution

Bucket
Counting
Radix
Gravity
American Flag
Pigeonhole
Burst
Flash

Concurrent

Bitonic
Pairwise Network
Sample

Hybrid

Block-Merge
Tim
Intro
Spread
Merge-Insert
Grail
Weave

Misc

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 NoSeveral 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 NoExpected: $O(n \cdot n!)$, Best=$O(n)$$\Theta(n)$Impractical
Stability

A sorting algorithm is said to be stable if it preserves the relative order of equal elements.

A Tour of Various Algorithms

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:

The $n^2$ Comparison Sorts

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!

Selection Sort

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:

Insertion Sort

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:

Bubble Sort

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:

Cocktail Sort

This is a bidirectional bubble sort. Also called Shaker Sort or Shuttle Sort.

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

Dick Grune

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--;
    }
  }
}

Improved Variants of the $n^2$ Comparison Sorts

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

Shell Sort

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.

Comb Sort

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.

The $n \log n$ Comparison Sorts

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.

Tree Sort

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.

Quick Sort

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:

Heap Sort

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);
  }
}

Merge Sort

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:

Introsort

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.

Timsort

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.

The Distribution Sorts

Bucket Sort

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.

Counting Sort

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;
  }
}

Radix Sort

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;
    }
  }
}

The Impractical Sorts

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

Stooge Sort

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.

Slow Sort

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}})$

Bogo Sort

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);
}

Bozo Sort

If the array is already sorted, you are done. If not, swap two random elements and repeat.

Exercise: Find out about the complexity of Bozo Sort.

BogoBogoSort

Information.

Bad Sort

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

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.

Miracle Sort

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.

Choosing a Sorting Algorithm

Which algorithm (or combination of algorithms!) is right for you depends on your particular application. Ask yourself:

Sorting in Various Languages

Congratulate yourself for getting this far. Now you are allowed to use the built-in sorting operations that your language provides for you.

Java

Java has different methods for performing in-place mutable sorts on arrays versus collections (such as lists). It has:

For non-in-place sorts, you need to use streams, for example:

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.

BuiltInSortingDemo.java
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");
    }
}

Python

TODO

JavaScript

TODO

C++

TODO

Summary

We’ve covered:

  • An overview of sorting, through videos and interactive demos
  • How sorting algorithms can be classified
  • An overview of selected algorithms
  • How to choose an algorithm
  • Built-in sorts in various programming languages