Card 01/ 11
Elementary Sorts: Growing a Sorted Part One Item at a Time
Bubble, selection and insertion sort all grow a sorted part; they differ in where the next item comes from.
Bubble sort, selection sort and insertion sort are the three elementary sorts: each grows a sorted part of the array by one item on every pass of an outer loop, and they differ only in where that next item comes from. This card maps the family and the three properties used to tell any two sorts apart: stable, in place and adaptive. All three take O(n²) time on most inputs. They are worth knowing because they are the smallest sorts you can trace by hand, and because one of them still runs inside the sorts that libraries ship.
Every member splits the array into a sorted part and an unsorted part. The outer loop runs about n times, and each time an inner loop either finds one item or places one item, and the sorted part grows by one. The table names what changes from member to member.
| Algorithm | Sorted part grows at | Next item comes from | Reach for it when |
|---|---|---|---|
| Bubble sort | The right end | The largest unsorted item, carried right by swapping neighbours | Teaching, or checking in one pass that data is already sorted |
| Selection sort | The left end | The smallest unsorted item, found by scanning all of them | Moving an item costs far more than comparing two, since it makes at most n − 1 swaps |
| Insertion sort | The left end | The next item in the array, slid left into its place | The input is small, nearly sorted, or arrives one item at a time |
Three words describe how a sort behaves beyond its Big O, and the three members answer them differently. A sort is stable when items with equal keys keep the order they started in: sort a list of orders by price, and two orders at the same price stay in the order they were placed. It matters whenever you sort by one field and then by another. A sort is in place when it needs only O(1) memory beyond the array itself; all three are. A sort is adaptive when it does less work the closer its input already is to sorted. Insertion sort is stable and adaptive. Bubble sort is stable, and adaptive only with the check that stops it after a pass with no swaps. Selection sort is neither.
Most people sort a hand of playing cards by insertion: they pick up one card at a time and slide it into place among the cards already held. The likeness breaks in what each can see. A person sees the whole hand and drops a card straight into its slot, and an algorithm sees two items at a time and finds the slot only by comparing its way there, one neighbour after another.
Merge sort is not an elementary sort, though it also produces a sorted array. It never grows one sorted part item by item: it sorts two halves separately and merges them, which is how it escapes O(n²).
Because every member grows a sorted part, you can check any of them halfway through a run by asking two questions: what does the sorted part hold, and where will its next item come from? The topic traces all three on the same seven numbers, 6 2 9 4 1 7 3, so their answers can be compared directly.
← → move through sections and cards