Why learn to sort?
You will almost never write your own sort. Every language has a good one built in. Sorting is still worth learning, for two reasons.
- It is the clearest example of different ways to solve the same problem, with very different costs.
- Sorted data makes other things fast. Binary search only works on sorted items.
This lesson puts four classic methods on the same ten bars and counts the comparisons each one makes.
Bubble sort
Rule: compare each pair of neighbours. If they are in the wrong order, swap them. Go through the list again and again until a pass makes no swaps.
On each pass the largest remaining value "bubbles" to the right end.
Start. Compare neighbours and swap them if they are in the wrong order. Repeat until a pass makes no swaps.
- Comparisons
- 0
- Swaps
- 0
def bubble_sort(items):
for end in range(len(items) - 1, 0, -1):
swapped = False
for i in range(end):
if items[i] > items[i + 1]:
items[i], items[i + 1] = items[i + 1], items[i]
swapped = True
if not swapped:
break # a clean pass: already sortedIt is the easiest to understand and one of the slowest. A value far from its place moves only one step per comparison.
Selection sort
Rule: scan the unsorted part for the smallest value. Move it to the front. Repeat with what is left.
Start. Find the smallest bar in the unsorted part and move it to the front. Repeat.
- Comparisons
- 0
- Swaps
- 0
def selection_sort(items):
for start in range(len(items) - 1):
smallest = start
for i in range(start + 1, len(items)):
if items[i] < items[smallest]:
smallest = i
items[start], items[smallest] = items[smallest], items[start]It does very few swaps, at most one per pass. But it always scans the whole unsorted part, even when the list is already sorted. It never finishes early.
Insertion sort
Rule: take the next value and slide it left until it sits in its place among the values already sorted. This is how most people sort a hand of cards.
Start. Take the next bar and slide it left into its place among the bars already sorted.
- Comparisons
- 0
- Swaps
- 0
def insertion_sort(items):
for next_index in range(1, len(items)):
i = next_index
while i > 0 and items[i - 1] > items[i]:
items[i - 1], items[i] = items[i], items[i - 1]
i -= 1A value that is already in place costs one comparison. So on a list that is nearly sorted, insertion sort is very fast: close to one comparison per item.
Merge sort
The first three share an idea: fix one value at a time. Merge sort does something different.
Split the list in half
Keep splitting until every piece holds one item. A list of one item is already sorted.
Merge two sorted pieces into one sorted piece
Look at the front item of each piece. Take the smaller one. Repeat.
Keep merging
Pieces of 1 become pieces of 2, then 4, then 8, until one sorted list remains.
Start. Split the list in half, sort each half, then merge the two sorted halves.
- Comparisons
- 0
- Items written
- 0
Merging is cheap because both pieces are already sorted. The smallest item overall must be at the front of one of them, so one comparison decides it.
def merge_sort(items):
if len(items) <= 1:
return items
middle = len(items) // 2
left = merge_sort(items[:middle])
right = merge_sort(items[middle:])
merged = []
a = b = 0
while a < len(left) and b < len(right):
if left[a] <= right[b]:
merged.append(left[a]); a += 1
else:
merged.append(right[b]); b += 1
return merged + left[a:] + right[b:]The scores
Same ten bars, four methods.
Lower is better. With ten items the gap is modest. It grows quickly as the list gets longer.
On ten items the gap looks small: 45 for the worst, 23 for the best. The gap is not about ten items. It is about how the work grows.
- The first three compare roughly every item with every other item. Double the list and the work goes up four times. This is O(n²).
- Merge sort halves the list about log n times, and each level of merging touches every item once. Double the list and the work goes up a little more than two times. This is O(n log n).
| Items | About n² / 2 comparisons | About n log n comparisons |
|---|---|---|
| 10 | 45 | 33 |
| 1,000 | 500,000 | 10,000 |
| 1,000,000 | 500,000,000,000 | 20,000,000 |
At a million items the slow methods do 25,000 times more work. That is the difference between an instant and a long wait. See Big-O Notation and Logarithms.
Try them yourself
Start. Compare neighbours and swap them if they are in the wrong order. Repeat until a pass makes no swaps.
- Comparisons
- 0
- Swaps
- 0
Side by side
| Comparisons, typical | Already sorted input | Extra memory | Keeps equal items in order | |
|---|---|---|---|---|
| Bubble | n² | Fast, one pass | None | Yes |
| Selection | n² | Still n² | None | No |
| Insertion | n² | Fast, one pass | None | Yes |
| Merge | n log n | n log n | A second copy of the list | Yes |
"Keeps equal items in order" is called being stable. It matters when you sort by one thing and then another: sort people by name, then by city, and a stable sort leaves each city's people still in name order.
What real libraries use
- Quicksort and its variants: O(n log n) on average, and sorts in place without a second copy.
- Timsort, used by Python and Java for objects: merge sort that looks for runs that are already sorted, and uses insertion sort on small pieces.
So the simple methods are not useless. Insertion sort is the fastest choice for very short lists, and real sorts hand small pieces to it.
Key takeaways
- Bubble, selection and insertion sort fix one value at a time and need about n² comparisons.
- Merge sort splits the list, sorts the halves and merges them, and needs about n log n.
- The difference is small on ten items and enormous on a million.
- Insertion sort is very fast on short or nearly sorted lists, which is why real sorts still use it inside.
- A stable sort keeps equal items in their original order.