Sorting Algorithms

Introduction

Every language already has a sort function, so for a while I didn't see the point of learning how sorting works. Then I kept running into it in interview prep, and I realized the simple sorting algorithms are the best way to actually feel the Big O stuff I wrote about earlier this year. They're small enough to trace by hand, and the differences between them teach you a lot about how to think about loops.

Bubble sort

Walk the array comparing each pair of neighbors. If they're out of order, swap them. After one full pass, the largest value has "bubbled" to the end. Repeat for the rest.

function bubbleSort(arr) {
  for (let end = arr.length - 1; end > 0; end--) {
    let swapped = false;
    for (let i = 0; i < end; i++) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swapped = true;
      }
    }
    if (!swapped) break; // already sorted, stop early
  }
  return arr;
}

The swapped flag is a small optimization: if a whole pass goes by with no swaps, the array is sorted and we can stop. On an already-sorted array that makes bubble sort O(n). On a reversed array it's still the full O(n²).

Selection sort

Find the smallest value in the unsorted part, swap it into the first open slot. Then find the next smallest, and so on. The sorted section grows from the left.

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let min = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min]) min = j;
    }
    if (min !== i) [arr[i], arr[min]] = [arr[min], arr[i]];
  }
  return arr;
}

Selection sort always does the same number of comparisons no matter what the input looks like. The upside is that it does at most n - 1 swaps, which matters if swapping is expensive (writing to flash memory, for example).

Insertion sort

Take the next unsorted value and slide it left until it lands in the right spot among the already-sorted values. It's how most people sort a hand of cards.

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let j = i;
    while (j > 0 && arr[j - 1] > arr[j]) {
      [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
      j--;
    }
  }
  return arr;
}

Insertion sort is the sleeper hit of the three. On data that's already mostly sorted it's close to O(n), because each value only has to slide a step or two. That's why real sorting libraries actually use it for small chunks inside their fancier algorithms.

Watch them work

Pick an algorithm and hit Play, or Step through it one comparison at a time. Yellow bars are being compared, red bars just swapped, green bars are locked in place. Keep an eye on the comparison and swap counts. Then hit Shuffle and run all three on the same array to see how the counts differ.

Comparing them

All three are O(n²) in the average case, which is why none of them are the default anywhere. But the demo shows they're not the same. Selection sort does the fewest swaps. Insertion sort does the fewest comparisons when the input is nearly sorted. Bubble sort is the easiest to explain and the hardest to justify.

What to use instead

In real code, use the built-in sort. Array.prototype.sort is O(n log n) and has had years of tuning. The thing to know is that it sorts as strings by default, so always pass a comparator for numbers:

[10, 9, 1].sort();              // [1, 10, 9]  <- strings!
[10, 9, 1].sort((a, b) => a - b); // [1, 9, 10]

The algorithms behind the built-in sorts (merge sort, quicksort, Timsort) are the next step up. They get to O(n log n) by splitting the array in half and sorting the pieces, which is a whole post on its own.

Conclusion

Sorting by hand taught me more about nested loops and Big O than any chart did. If you're learning algorithms, implement these three without looking, then step through the demo and check your mental model against what actually happens.