Elementary sorts
Sorting arranges items in order and underlies searching, merging, de-duplication, and countless other tasks. Simple quadratic sorts are slow on big inputs but teach key ideas and still have practical niches.
Sorting vocabulary
A sorting algorithm rearranges items by a key into non-decreasing order. Important properties: time complexity in the best, average, and worst cases; space, especially whether it sorts in place with O(1) extra memory; stability, whether equal keys keep their original relative order; and adaptivity, whether it runs faster on nearly sorted input.
Bubble sort
Bubble sort repeatedly passes through the list, swapping adjacent items that are out of order, so large items 'bubble' to the end. After pass k, the last k items are in place. It takes O(n^2) comparisons in the worst and average cases; with an early-exit check when a pass makes no swaps, it takes O(n) on already sorted data. It is stable and in place but rarely used in practice.
Selection sort
Selection sort finds the smallest remaining item and swaps it into the next position, repeating n - 1 times. It always makes about n^2 / 2 comparisons, regardless of input, but only n - 1 swaps, which can matter when writes are expensive. The standard version is not stable, because long-distance swaps can jump an item past an equal one.
Insertion sort
Insertion sort grows a sorted prefix: each new item is shifted left past larger items until it fits. Worst case O(n^2), for reverse-sorted input, but O(n) for sorted input and fast whenever items are close to their final positions. Its cost is O(n + I), where I is the number of inversions, pairs out of order. It is stable, in place, and simple.
Why insertion sort still matters
On small arrays, around 10 to 30 items, insertion sort's low overhead beats more sophisticated algorithms. So practical sorts, including Timsort and introsort, switch to insertion sort for small pieces. It also suits data that arrives nearly sorted, such as a list with a few new entries appended.
Shellsort
Shellsort, by Donald Shell in 1959, runs insertion sort on items a gap apart, then shrinks the gap, finishing with a gap of 1. Early passes move items long distances cheaply, so the final insertion sort has little left to do. With good gap sequences it runs in roughly O(n^(4/3)) or better in practice, with no extra memory, though its exact complexity depends on the gaps.
Inversions
An inversion is a pair of positions i < j with a[i] > a[j]. A sorted array has 0; a reversed array of n items has n(n - 1)/2, the maximum. Swapping adjacent items removes exactly one inversion, which proves that any algorithm sorting only by adjacent swaps, such as bubble and insertion sort, needs on the order of n^2 swaps on average.
Worked example
Insertion sort on [5, 2, 4, 1]: insert 2: shift 5, giving [2, 5, 4, 1]. Insert 4: shift 5, giving [2, 4, 5, 1]. Insert 1: shift 5, 4, and 2, giving [1, 2, 4, 5]. Total shifts: 1 + 1 + 3 = 5, which equals the original number of inversions: (5,2), (5,4), (5,1), (2,1), (4,1).
Key takeaways
Sorting algorithms are judged by time, space, stability, and adaptivity. Bubble sort swaps neighbours, O(n^2), with an O(n) early exit on sorted data. Selection sort always does about n^2 / 2 comparisons but only n - 1 swaps and is unstable. Insertion sort is stable, adaptive, O(n + inversions), and best for small or nearly sorted arrays, which is why hybrid sorts use it. Shellsort sorts gapped subsequences for sub-quadratic performance. Adjacent-swap sorts need about n^2 / 4 swaps on average, because each swap fixes one inversion.
Flashcard
Equal keys keep their relative order
Check your understanding
Which elementary sort runs in close to linear time on an array that is already almost sorted?