Putting a list in order
A sorting algorithm puts the items of a list in order, and three classic ones are selection sort, insertion sort and merge sort. Choosing between them is a question of cost: on a big list one of them does thousands of times less work than the others.
A shop sorts its orders by date before it prints the picking list. With 50 orders any method will do. With 5 million the choice decides whether the list is ready by morning.
By the end of this lesson
Note
I can trace insertion sort, selection sort and merge sort and compare what they cost.
Key words
| Word | What it means |
|---|---|
| Sort | to put items in order |
| Comparison | asking which of two items is smaller |
| Pass | one trip through the list |
| Merge | to join two sorted lists into one sorted list |
| Divide and conquer | split a problem, solve the parts, join the answers |
| In place | sorting inside the same list, with no second copy |
The cells students fill in are left blank in this preview.
Selection sort picks the smallest each time
Selection sort makes a pass over the unsorted part, finds the smallest item and swaps it to the front. Then it repeats on what is left.
For n items the passes make (n - 1) + (n - 2) + ... + 1 comparisons. That adds up to n times (n - 1), divided by 2. It is quadratic.
Watch selection sort work
# Selection sort: find the smallest, move it to the front, repeat.
numbers = [29, 10, 14, 37, 13]
comparisons = 0
for start in range(len(numbers)):
smallest = start
for i in range(start + 1, len(numbers)):
comparisons = comparisons + 1
if numbers[i] < numbers[smallest]:
smallest = i
saved = numbers[start]
numbers[start] = numbers[smallest]
numbers[smallest] = saved
print(numbers)
print("comparisons", comparisons)
# Change numbers to [10, 13, 14, 29, 37], already sorted, and run again.
Insertion sort slides each item into place
Insertion sort treats the left part of the list as already sorted. It takes the next item and slides it left past every bigger item.
If the list is nearly in order, few items move, so it is fast. If it is in reverse order, every item travels the whole way and the cost is quadratic.
Watch insertion sort work
# Insertion sort: take the next item and slide it left into place.
numbers = [29, 10, 14, 37, 13]
shifts = 0
for i in range(1, len(numbers)):
item = numbers[i]
j = i - 1
while j >= 0 and numbers[j] > item:
numbers[j + 1] = numbers[j]
j = j - 1
shifts = shifts + 1
numbers[j + 1] = item
print(numbers)
print("shifts", shifts)
# Change numbers to [10, 13, 14, 29, 37] and run again.
Merge sort splits, then merges
Merge sort uses divide and conquer. It splits the list in half again and again until each piece holds one item. A single item is already sorted.
Then it merges pairs of sorted pieces into bigger sorted pieces. The diagram shows four items.
Merging two sorted lists takes one pass
To merge, compare the two front items and take the smaller. Repeat until one list is empty, then add the rest of the other.
Each item is taken once, so merging lists of n items in total takes about n steps.
Merge two sorted lists
# Merge two sorted lists into one sorted list.
left = [3, 8, 12]
right = [5, 6, 20]
result = []
i = 0
j = 0
comparisons = 0
while i < len(left) and j < len(right):
comparisons = comparisons + 1
if left[i] <= right[j]:
result.append(left[i])
i = i + 1
else:
result.append(right[j])
j = j + 1
# One list is used up. The rest of the other goes on the end.
while i < len(left):
result.append(left[i])
i = i + 1
while j < len(right):
result.append(right[j])
j = j + 1
print(result, "comparisons", comparisons)
Worked example: merging two sorted lists
| Front items | Taken | Result so far |
|---|---|---|
| 3 and 5 | 3 | 3 |
| 8 and 5 | 5 | 3, 5 |
| 8 and 6 | 6 | 3, 5, 6 |
| 8 and 20 | 8 | 3, 5, 6, 8 |
| 12 and 20 | 12 | 3, 5, 6, 8, 12 |
| Left list is empty | Add 20 | 3, 5, 6, 8, 12, 20 |
The cells students fill in are left blank in this preview.
Merge two sorted lists in the terminal
sort -m -n <(printf '1\n4\n9\n') <(printf '2\n3\n10\n')Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Merge sort costs far fewer steps
Merge sort halves the list about log n times, and each level of merging costs about n steps. So it takes about n times log n steps in all.
Selection and insertion sort take about n times n. The table puts numbers on the difference.
Worked example: comparisons as n grows
| n | Selection sort: n(n-1)/2 | Merge sort: about n log n |
|---|---|---|
| 10 | 45 | about 33 |
| 1,000 | 499,500 | about 10,000 |
| 1,000,000 | about 500 billion | about 20 million |
The cells students fill in are left blank in this preview.
Selection sort comparisons for 1000 items
python3 -c "print(1000 * 999 // 2)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Python sorts for you
python3 -c "print(sorted([5, 2, 9, 1]))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think a list that is already sorted needs no work from any sort. Selection sort still makes every comparison, 10 for 5 items. Only some methods, such as insertion sort, take shortcuts when the list is nearly in order.