Practice: Sorting Race Times That Arrive Almost in Order

Finishing times reach the timing desk nearly sorted, with a few runners swapped.

Choosing among the elementary sorts comes down to reading the input, and nearly sorted input is the case where the choice matters most. This exercise practises both steps: noticing that the data is almost in order, and counting what the right sort does with it.

At a running race, each runner's chip is read as they cross the line, and the finishing times reach the timing desk in that order. When two runners finish close together, the readers sometimes report them the wrong way round. Eight times, in seconds, arrive as 812 818 815 826 834 829 841 847, at indices 0 to 7, and the desk must sort them before printing the results.

Which of bubble, selection and insertion sort would you use on these times, and why?
Trace your choice and count its comparisons and its swaps or shifts.

Show the answer

Insertion sort, because the times are nearly sorted: only two pairs are out of order, 818 before 815 and 834 before 829, so it makes 2 shifts and 9 comparisons, barely more than the 7 that eight sorted times would cost. The trace follows an instrumented run, with i on the index each key was lifted from and key on where it landed.

Insertion sort on eight finishing times

Input812 818 815 826 834 829 841 847, in seconds, indices 0 to 7

Insert 818
1. 812
2. 818ikey
3. 815
4. 826
5. 834
6. 829
7. 841
8. 847
812 is not larger than 818, so 818 stays where it is.
Insert 815
1. 812
2. 815key
3. 818i
4. 826
5. 834
6. 829
7. 841
8. 847
818 shifts right and 815 lands at index 1.
Insert 826
1. 812
2. 815
3. 818
4. 826ikey
5. 834
6. 829
7. 841
8. 847
818 is not larger than 826, so nothing shifts.
Insert 834
1. 812
2. 815
3. 818
4. 826
5. 834ikey
6. 829
7. 841
8. 847
826 is not larger than 834, so nothing shifts.
Insert 829
1. 812
2. 815
3. 818
4. 826
5. 829key
6. 834i
7. 841
8. 847
834 shifts right and 829 lands at index 4.
Insert 841
1. 812
2. 815
3. 818
4. 826
5. 829
6. 834
7. 841ikey
8. 847
834 is not larger than 841, so nothing shifts.
Insert 847
1. 812
2. 815
3. 818
4. 826
5. 829
6. 834
7. 841
8. 847ikey
841 is not larger than 847, and the times are in order after 2 shifts.

ResultSorted after 7 insertions: 9 comparisons, 2 shifts

Each of the seven keys makes one stopping comparison, since none reaches the front, and the two keys that move each make one more comparison for their shift: 7 + 2 is 9. The listing below printed the same counts.

race_times.pypy

def insertion_sort(times: list[int]) -> tuple[int, int]:
    comparisons = shifts = 0
    for i in range(1, len(times)):
        key = times[i]
        j = i - 1
        while j >= 0:
            comparisons += 1
            if times[j] <= key:
                break
            times[j + 1] = times[j]
            shifts += 1
            j -= 1
        times[j + 1] = key
    return comparisons, shifts


times = [812, 818, 815, 826, 834, 829, 841, 847]
comparisons, shifts = insertion_sort(times)
print("sorted:", " ".join(map(str, times)))
print(f"{comparisons} comparisons, {shifts} shifts")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

sorted: 812 815 818 826 829 834 841 847
9 comparisons, 2 shifts

Java and TypeScript versions of the same function printed the same two lines. The rivals did worse on the same times. Bubble sort made 13 comparisons and 2 swaps, because after the first pass fixes both pairs it needs a second whole pass to see that nothing moves. Selection sort made 28 comparisons, eight times seven over two, and 2 swaps, as it would on any order of eight times.

Two slips are common. Counting 7 comparisons forgets that a key which shifts compares once for the shift and once more to stop. Choosing selection sort for its few swaps ties with insertion sort here at 2 moves, and pays three times the comparisons for it.

← → move through sections and cards