Basic sorting

A sorted list answers questions an unsorted one can't answer quickly: binary search finds any value in O(log n), duplicates sit next to each other, and the smallest and largest items are at the ends. That is why sorting is one of the most common first steps in an algorithm.

The sorts on this page work only by comparing two items and moving items around, so they sort anything that can be compared: numbers, words, dates. Both build the sorted list one item at a time, from the left, and both keep the same promise: after step i, the first part of the list is in order.

Picture sorting a hand of cards as you pick them up. Each new card is slid left past the cards larger than it and dropped into the gap. Insertion sort does exactly that: take the next item, shift every larger item in the sorted part one cell right, and drop it in.

Each shift fixes one inversion: a pair of items in the wrong order. A list has at most n(n − 1) ÷ 2 of them (when it is reversed), so the worst case is O(n²). But a list that is already sorted has none: every item is compared once and stays put, which is O(n). Nearly sorted lists cost close to that.

Selection sort works the other way round. It scans the unsorted part for its smallest item and swaps it to the front of that part. Then the front cell is final, and the next scan starts one cell later.

Every scan looks at the whole unsorted part, so selection sort always does n(n − 1) ÷ 2 comparisons, even on a list that is already sorted. What it saves is writes: at most n − 1 swaps, one per position. That only matters when writing is much more expensive than comparing.

Bubble sort walks the list again and again, swapping any neighboring pair that is in the wrong order, until a full pass swaps nothing. Large items "bubble" to the end one pass at a time.

It is also O(n²), and like insertion sort it fixes one inversion per swap, but each fix costs a full three-step swap where insertion sort does a single shift. You'll meet it in textbooks and interviews; in real code, insertion sort does the same job faster.

Sort a shop's orders by customer. Two orders from the same customer compare as equal, so which comes first? A stable sort promises they keep their original order. That lets you sort in passes: sort by date first, then stably by customer, and each customer's orders stay in date order.

Insertion sort is stable: it only shifts items that are strictly larger, so an item never passes an equal one. Selection sort is not. In [2a, 2b, 1], its first swap sends 2a to the back to make room for 1, giving [1, 2b, 2a]: the two 2s have changed places.

When only three values can appear, there is no need to compare everything with everything. Keep three regions, 0s at the front, 2s at the back, 1s between, and one pass of swaps puts each item in its region. It isn't stable, but for plain values that doesn't matter.

For anything large, the O(n log n) sorts on the next pages win by a wide margin. But on a few dozen items, insertion sort's tiny constant beats them, so fast library sorts switch to insertion sort for small pieces. Python's sort, Timsort, also takes advantage of runs that are already in order, which is insertion sort's strength.