Sorting — Inventing Order

Before sorting anything, you need a way to check whether a list is sorted.

Write is_sorted(lst) that returns True if every element is less than or equal to the next one.

is_sorted([1, 2, 2, 9])   # True
is_sorted([1, 3, 2])      # False
is_sorted([5])            # True
is_sorted([])             # True

All the algorithms in this chapter rearrange elements inside the same list. The basic move is a swap.

Write swap(lst, i, j) that exchanges the elements at positions i and j in place (modify the list, return nothing).

x = [10, 20, 30]
swap(x, 0, 2)
x   # [30, 20, 10]

The idea: walk through the list comparing neighbors. Whenever the left neighbor is bigger, swap them. What happens to the largest value after one full pass?

Write bubble_pass(lst) that goes through the list once, comparing each pair of neighbors (lst[i], lst[i+1]) and swapping when they are out of order. Modify the list in place.

Before you code: Take [3, 1, 4, 1, 5, 9, 2, 6] and do one pass by hand. Where does the 9 end up? Why must the largest element always reach the last position after one full pass?

x = [3, 1, 4, 1, 5, 9, 2, 6]
bubble_pass(x)
x   # [1, 3, 1, 4, 5, 2, 6, 9]

One pass guarantees the largest element is at the end. How many passes guarantee the whole list is sorted?

Write pass_sort(lst) that repeats passes until the list is sorted. Modify in place.

Think about:

• After pass 1, the last element is final. After pass 2, the last two are final. Can each pass stop earlier than the previous one?
• If a whole pass makes zero swaps, what do you know?

x = [5, 2, 9, 1, 5, 6]
pass_sort(x)
x   # [1, 2, 5, 5, 6, 9]

How much work does bubble sort actually do?

Write pass_sort_counting(lst) — same algorithm, but return the total number of comparisons made.

Run it on lists of length 10, 100, and 1000 (use random.sample(range(10000), n)). When the list gets 10x longer, how much does the comparison count grow?

Fill in the table:

This growth pattern is called O(n²) — quadratic time.

Pause and think: a modern laptop does roughly $10^8$–$10^9$ simple operations per second. If n = 1,000,000, then $n^2 = 10^{12}$. How long would bubble sort take? Hours? Days?

This is why we need better ideas.

Think about how you sort playing cards in your hand: you pick up cards one at a time, and insert each new card into its correct place among the cards you already hold — which are always sorted.

Suppose lst[0:k] is already sorted and lst[k] is the new card.

Write insert_card(lst, k) that moves lst[k] left, one swap at a time, until it sits in its correct position. In place.

x = [2, 5, 8, 3]      # first 3 elements sorted, insert the 3
insert_card(x, 3)
x   # [2, 3, 5, 8]

Now sort the whole list: the sorted prefix starts with just lst[0:1], and you insert lst[1], then lst[2], ... one at a time.

Write card_sort(lst). In place.

x = [5, 2, 9, 1, 5, 6]
card_sort(x)
x   # [1, 2, 5, 5, 6, 9]

Run your card_sort on a list that is already sorted, counting comparisons (write card_sort_counting, like you did for bubble sort).

• Already sorted list of length 1000: how many comparisons?
• Reversed list of length 1000: how many comparisons?

Insertion sort is O(n²) in the worst case, but O(n) when the data is nearly sorted — which is why real-world sorts (like Python's Timsort) use it as a building block.

Two students both scored 85: Alice (entered first) and Bob (entered second). After sorting by score, a stable sort guarantees Alice still appears before Bob. Which of the following is true?

A. Bubble sort and insertion sort are stable, but quicksort is not (in its typical implementation)

B. All comparison sorts are stable by definition

C. Stability only matters for numbers, not for records with multiple fields

D. Quicksort is stable but bubble sort is not

Here is a completely different idea, and it comes from a question: If I hand you two already-sorted lists, can you combine them into one sorted list faster than sorting from scratch?

Write merge(a, b) where a and b are each sorted. Return a new sorted list containing all elements of both.

Before you code: merge [1, 5, 9] and [2, 3, 7] by hand. You only ever need to compare the two front elements. Why?

merge([1, 5, 9], [2, 3, 7])   # [1, 2, 3, 5, 7, 9]
merge([], [4, 8])             # [4, 8]
merge([1, 1], [1])            # [1, 1, 1]

How many comparisons did merging cost, roughly, for lists of total length n?

Now the recursive leap (remember the Recursion chapter):

To sort a list: split it in half, sort each half (how? the same way!), then merge the two sorted halves.

Write split_sort(lst) that returns a new sorted list. What is the base case — the list so small it is already sorted?

split_sort([5, 2, 9, 1, 5, 6])   # [1, 2, 5, 5, 6, 9]
split_sort([])                   # []

Picture the recursion as levels:

level 0:              [ n elements ]                 -> merged with ~n comparisons
level 1:        [ n/2 ]        [ n/2 ]               -> merged with ~n comparisons
level 2:     [n/4] [n/4]    [n/4] [n/4]              -> merged with ~n comparisons
...

• Each level does about n comparison work in total.
• How many times can you halve n before reaching lists of size 1? (You invented this number in the Binary Search chapter — it is $\log_2(n)$.)

So the total is about $n \cdot \log_2(n)$. For n = 1,000,000:

• $n^2 = 1{,}000{,}000{,}000{,}000$
• $n \cdot \log_2(n) \approx 20{,}000{,}000$

50,000x less work. Compute the ratio yourself for a few values of n.

Part 3 splits blindly down the middle, then does its work while merging. What if you did the work while splitting, so no merge is needed?

Warm-up from real life. You have records labeled 0 or 1:

[(0,"x"), (1, 12), (0, 34), (1, 90), (1, 89), (0, "s"), (1, "7")]

Move all the 0-records to the front and all the 1-records to the back — without creating another list, touching each element only a constant number of times (a single O(n) pass with swaps).

Hint: keep two positions, one scanning from the left, one from the right. What should each of them look for?

Write partition_01(lst) that rearranges in place. (Order within the 0-group and 1-group may end up anything.)

Generalize: instead of 0s and 1s, pick one element of the list — the pivot — and rearrange so that everything < pivot is on its left and everything >= pivot is on its right.

Write partition(lst, lo, hi) that:

• works on the slice lst[lo..hi] (inclusive) in place,
• uses lst[hi] as the pivot,
• returns the final index where the pivot lands.

x = [3, 8, 2, 5, 1, 4]
p = partition(x, 0, 5)    # pivot = 4
# afterwards: {3, 2, 1} somewhere left of 4, {8, 5} right of it
x[p]   # 4

After partitioning, the pivot is in its final sorted position. What remains? Two smaller unsorted regions — one on each side. Sort each of them... the same way.

Write pivot_sort(lst, lo=0, hi=None) that sorts in place.

x = [5, 2, 9, 1, 5, 6]
pivot_sort(x)
x   # [1, 2, 5, 5, 6, 9]

Think about: merge sort needed extra memory for merging. How much extra memory does quick sort need?

Quicksort is O(n·log n) on average, but what input causes its worst-case O(n²) performance when always picking the first element as pivot?

A. A list of random numbers

B. A list that is already sorted (or reverse-sorted)

C. A list with many duplicate values

D. A very short list (fewer than 5 elements)

A puzzle: You must sort the ages of a billion people. Ages are whole numbers between 0 and 200. Your Part 3 algorithm would need ~30 billion comparisons. Can you sort them with zero comparisons between elements?

Hint: how many different values can an age take?

Write count_values(ages, max_value) that returns a list counts of length max_value + 1, where counts[v] is how many times age v appears.

count_values([3, 1, 3, 0], 3)   # [1, 1, 0, 2]

If you know there are three 0s, zero 1s, five 2s, ... you can write down the sorted list directly.

Write tally_sort(ages, max_value) that returns the sorted list using count_values — no comparisons between elements at all.

tally_sort([3, 1, 3, 0], 3)   # [0, 1, 3, 3]

Then answer:

• How many operations for n ages with values up to k? (in terms of n and k)
• Why can't you use this trick to sort arbitrary floats or strings?

Counting sort can sort a billion ages in O(n) time. Why can't we always use it instead of O(n·log n) algorithms like merge sort?

A. Counting sort only works on Python lists, not NumPy arrays

B. Counting sort requires knowing the range of values and works best when that range is small — sorting a billion arbitrary floating-point numbers would need impossibly many buckets

C. Counting sort is unstable, so we can't use it for important data

D. Counting sort uses too much memory for any list larger than 1,000 elements

Time to put every algorithm you invented on the same track.

The helper below times each sorting algorithm on progressively larger lists and plots the results on a log-log scale. Run it once all your sorts pass their tests.

Reading the plot: on a log-log plot, O(n²) algorithms climb with slope 2, O(n·log n) with slope ~1. You should see the two families separate clearly.

Using your timing for pass_sort at n = 4000, predict how long it would take at n = 1,000,000 (scale by $(10^6/4000)^2$). Write the number down.

Then predict split_sort at n = 1,000,000 from its n = 64000 timing.

One of these predictions is minutes-to-hours. The other is around a second. Which is which?

Python's built-in sort() (Timsort) combines two of your inventions: merge sort's structure with insertion sort's speed on nearly-sorted runs.