The Simple (Slow) Sorts

The problem

Hand someone a shuffled deck of thirteen cards and say "put these in order." Watch what they actually do. Almost nobody invents merge sort on the spot. They pick up cards one at a time and slot each into the right place among the ones already in their hand. Or they scan for the lowest card, pull it out, then scan again. These are real algorithms — you just ran one in your head.

That instinct is worth studying, because the sorts you'd reinvent from scratch are also the slow ones. Seeing exactly where they bog down is the fastest way to understand what the clever sorts are so careful to avoid.

A first attempt

Take bubble sort, the most literal idea of all: repeatedly walk the list and swap any two neighbours that are out of order. Big values "bubble" toward the end one pass at a time.

def bubble_sort(nums):
    n = len(nums)
    for i in range(n):
        for j in range(n - 1 - i):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums

Two nested loops over n elements is O(n²). Double the input and the work quadruples. Selection sort (repeatedly find the minimum and place it) has the same O(n²) shape. They share one fatal habit: they compare and move the same elements over and over, throwing away what they learned on the previous pass.

The insight

Not all O(n²) sorts are equally dumb. Insertion sort keeps the left part of the array already sorted and grows it one element at a time — exactly the card-in-hand move. To place the next element, it slides it leftward past everything larger until it lands.

The payoff is that insertion sort does almost no work when the data is already close to sorted: each new element barely moves. On nearly-ordered input it runs in O(n), not O(n²). That single property — being adaptive — is why real libraries use insertion sort for small or almost-sorted slices even today.

How it works

We'll focus on insertion sort — the one worth keeping.

Sorting [5, 2, 4, 1], with | marking the boundary of the sorted region:

[5 | 2  4  1]     key=2 → slides past 5      → [2  5 | 4  1]
[2  5 | 4  1]     key=4 → slides past 5      → [2  4  5 | 1]
[2  4  5 | 1]     key=1 → slides past 5,4,2  → [1  2  4  5 |]

The code

def insertion_sort(nums):
    for i in range(1, len(nums)):
        key = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > key:
            nums[j + 1] = nums[j]   # slide right
            j -= 1
        nums[j + 1] = key           # drop into the gap
    return nums

function insertionSort(nums: number[]): number[] {
  for (let i = 1; i < nums.length; i++) {
    const key = nums[i];
    let j = i - 1;
    while (j >= 0 && nums[j] > key) {
      nums[j + 1] = nums[j]; // slide right
      j--;
    }
    nums[j + 1] = key; // drop into the gap
  }
  return nums;
}

void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int key = nums[i];
        int j = i - 1;
        while (j >= 0 && nums[j] > key) {
            nums[j + 1] = nums[j]; // slide right
            j--;
        }
        nums[j + 1] = key;         // drop into the gap
    }
}

void insertion_sort(int *nums, int n) {
    for (int i = 1; i < n; i++) {
        int key = nums[i];
        int j = i - 1;
        while (j >= 0 && nums[j] > key) {
            nums[j + 1] = nums[j]; /* slide right */
            j--;
        }
        nums[j + 1] = key;         /* drop into the gap */
    }
}

#include <vector>
using namespace std;

void insertionSort(vector<int> &nums) {
    for (size_t i = 1; i < nums.size(); i++) {
        int key = nums[i];
        int j = (int)i - 1;
        while (j >= 0 && nums[j] > key) {
            nums[j + 1] = nums[j]; // slide right
            j--;
        }
        nums[j + 1] = key;         // drop into the gap
    }
}

Complexity

Insertion and bubble hit their O(n) best case only on already-sorted input. Selection always does O(n²) comparisons regardless — it never gets to quit early.

When to use it

Practice

Recap

• Bubble, selection, and insertion are the sorts you'd invent yourself — all O(n²) on general data because they rework the same elements repeatedly.
• Insertion sort is the keeper: it's stable, in-place, and adaptive, hitting O(n) on nearly-sorted input.
• Their slowness motivates the divide-and-conquer sorts — understanding the O(n²) trap is what makes O(n log n) feel like a real achievement.