Simple Sorts

A friend hands you five numbered books to put back on a shelf: 7, 3, 9, 4, 1. You do not need an algorithm for that. You take the books one at a time, and each new one slides left past the bigger numbers until it sits in the right spot. In a few seconds the shelf reads 1, 3, 4, 7, 9.

That habit is a real sorting algorithm, called insertion sort. It and its two cousins, selection sort and bubble sort, are the "simple sorts". They are slow on big inputs. But they are short, they need no extra memory, and one of them still runs inside the built-in sort of Python and JavaScript.

#The idea: grow a sorted part

All three simple sorts split the array into two parts: a sorted part at the front and an unsorted part after it. Each round moves one item from the unsorted part into the sorted part. After n rounds, everything is sorted.

They differ only in how they pick and place that item:

• Insertion sort takes the next item, whatever it is, and slides it left into the right place among the sorted items.
• Selection sort searches the unsorted part for the smallest item and swaps it to the end of the sorted part.
• Bubble sort walks through the unsorted part swapping neighbours that are out of order, which carries the largest item to the end.

#Insertion sort, traced

Here is the bookshelf as an array. Watch the variable key: it holds the book in your hand while the bigger books shift one slot to the right to make a gap.

for i from 1 to n - 1:  key = a[i]  j = i - 1  while j >= 0 and a[j] > key:    a[j + 1] = a[j]    j = j - 1  a[j + 1] = key

The last step is the most useful fact about insertion sort. Each shift fixes exactly one pair that was out of order. An array that is already sorted has no such pairs, so insertion sort just does one comparison per item and finishes in O(n). An array that is almost sorted is almost that fast.

function insertionSort(a) {
  for (let i = 1; i < a.length; i++) {
    const key = a[i];
    let j = i - 1;
    // shift bigger items one slot right to open a gap
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key; // the gap is just right of j
  }
  return a;
}
 
insertionSort([7, 3, 9, 4, 1]); // [1, 3, 4, 7, 9]

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        # shift bigger items one slot right to open a gap
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key  # the gap is just right of j
    return a
 
insertion_sort([7, 3, 9, 4, 1])  # [1, 3, 4, 7, 9]

#Selection sort and bubble sort

Selection sort scans the whole unsorted part to find the smallest item, then makes one swap. So it writes very little: at most one swap per round. But the scan always runs to the end, so it is no faster on sorted input than on shuffled input.

Bubble sort compares neighbours and swaps them when they are out of order. One pass carries the largest item to the end, like a bubble rising. If a pass makes no swaps, the array is sorted and you can stop early. It is easy to explain and almost never the right choice. It makes one swap per out-of-order pair, the same count as insertion sort's shifts, but a swap writes two slots where a shift writes one. And each pass compares every neighbouring pair it walks over, while insertion sort stops comparing as soon as an item fits.

function selectionSort(a) {
  for (let i = 0; i < a.length - 1; i++) {
    let min = i;
    for (let j = i + 1; j < a.length; j++) {
      if (a[j] < a[min]) min = j;
    }
    [a[i], a[min]] = [a[min], a[i]]; // one swap per round
  }
  return a;
}
 
function bubbleSort(a) {
  for (let end = a.length - 1; end > 0; end--) {
    let swapped = false;
    for (let j = 0; j < end; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // no swaps: already sorted
  }
  return a;
}

def selection_sort(a):
    for i in range(len(a) - 1):
        smallest = i
        for j in range(i + 1, len(a)):
            if a[j] < a[smallest]:
                smallest = j
        a[i], a[smallest] = a[smallest], a[i]  # one swap per round
    return a
 
def bubble_sort(a):
    for end in range(len(a) - 1, 0, -1):
        swapped = False
        for j in range(end):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:  # no swaps: already sorted
            break
    return a

#Why they are O(n²)

In the worst case, the array is in reverse order. Insertion sort then shifts the second item 1 slot, the third item 2 slots, and so on up to n − 1. That is 1 + 2 + … + (n − 1) = n(n − 1) / 2 shifts, which is O(n²). Selection sort always does that many comparisons, whatever the input. With 10,000 items that is about 50 million steps; with a million items, about 500 billion.

None of them need a second array. They move items around inside the one they were given, so the extra space is O(1). An algorithm like that is called in place.

#Stable sorts keep ties in order

Real data has more than one field. Say a teacher's list is already in alphabetical order, and now she sorts it by score: Ann 82, Ben 75, Cal 82, Dee 75. A stable sort keeps items with equal keys in their original order, so the result is Ben 75, Dee 75, Ann 82, Cal 82. Within each score, names are still alphabetical.

Insertion sort is stable because it only shifts an item past items that are strictly bigger (a[j] > key). Selection sort is not, because its long-distance swap can jump an item over an equal one. On Ann 82, Ben 75, Cal 82, Dee 75, the first round swaps Ben to the front. The second round finds Dee and swaps her with Ann, which throws Ann to the very end, behind Cal. The result is Ben 75, Dee 75, Cal 82, Ann 82: the 82s are out of alphabetical order.

#Common mistakes

#Check yourself

#What to practise next

O(n²) is too slow for big inputs. Merge Sort gets to O(n log n) by splitting the array in half, sorting each half, and merging the two sorted halves, and it stays stable. Trace insertion sort by hand on [5, 1, 4, 2] before you move on: you should count 4 shifts.