AA / course home
Week 13 · Phase 4 · Choosing well

Sorting: Why Some Sorts Are Slow

Bubble and selection sort by hand, then Python's sorted() — n² vs n log n on a plot.

Why is the sort you invent yourself so much slower than the built-in one?

Lesson

Watch neighbouring swaps move the maximum

Bubble sort: shorten the unsorted part after each pass
start
51428
pass 1
14258
pass 2
12458
pass 3
12458
PassComparisonsSwaps
143
231
320 → stop

This version stops after a pass with no swaps: 9 comparisons and 4 swaps here. A different stopping rule can change the count.

Different methods exploit different structure

MethodBest timeWorst timeWhat moves
Bubble, with early stopΘ(n)Θ(n²)Adjacent out-of-order pairs
SelectionΘ(n²)Θ(n²)Choose the smallest remaining item
InsertionΘ(n)Θ(n²)Insert into a sorted prefix
Selection comparisons, regardless of initial order(n − 1) + … + 1 = n(n − 1)/2

Insertion sort does little work on nearly sorted input. In its usual shifting version, every shift removes one inversion: a pair whose order is wrong.

Merge: divide the list, then combine sorted halves

Merge sort example
split
[5, 1][4, 2]
sort halves
[1, 5][2, 4]
merge
1245
For n = 2ᵏ: k merge levels, linear work per levelT(n) = Θ(n log₂ n)

Merging repeatedly takes the smaller front item. A typical array implementation uses O(n) extra storage. Unequal halves for other n do not change the growth class.

Use keys; preserve ties when needed

Run in Colab · predict the result first
students = [("Ada", 80), ("Lin", 70), ("Sam", 80)]
ranked = sorted(students, key=lambda pair: pair[1])
print(ranked)
Stable score sort: Ada stays before Sam
result
Lin: 70Ada: 80Sam: 80

sorted returns a new list. list.sort() changes that list and returns None. lambda pair: pair[1] selects the second field (the score). Python sorting is stable: equal keys keep their original order. Its adaptive sort has O(n log n) worst-case time and can exploit existing order.

Practice

Practice questions

20 test questions · 30 written questions · 50 total

Each question is followed by its answer and explanation. Hard questions also include a starting hint and smaller reasoning steps.

Test questions

Choose one option. Cost questions state their model and whether the bound is tight, expected or worst-case. Here lg means log₂, and heap positions start at 1.

Question 1 · easy

Which array (positions 1 to 5) is a valid min-heap?

  1. [1, 3, 2, 5, 4]
  2. [1, 5, 2, 3, 4]
  3. [2, 1, 3, 4, 5]
  4. [1, 2, 3, 1, 0]

Answer: option A. In (b) the 5 at position 2 is bigger than its child 3; in (c) the root exceeds a child; in (d) position 2’s child 1 is smaller than 2.

Question 2 · easy

In the array layout of a heap, the parent of position 9 is position:

  1. 3
  2. 4
  3. 5
  4. 18

Answer: option B. Parent of k is ⌊k/2⌋.

Question 3 · easy

The root of a max-heap holds:

  1. the minimum
  2. the median
  3. the maximum
  4. an arbitrary key

Answer: option C. Every parent is at least as large as its children.

Question 4 · easy

What is the tightest listed worst-case upper bound for standard heapsort?

  1. O(n)
  2. O(n log n)
  3. O(n²)
  4. O(log n)

Answer: option B. Linear build plus n extractions at O(log n).

Question 5 · easy

Ignoring rounding and constant factors, which recurrence models mergesort, with T(1) constant?

  1. T(n) = T(n/2) + 1
  2. T(n) = 2T(n/2) + n
  3. T(n) = T(n − 1) + n
  4. T(n) = 2T(n − 1) + 1

Answer: option B. Two halves plus a linear merge; (a) is binary search and (c) is selection sort.

Question 6 · easy

For n distinct keys and standard two-way last-element-pivot quicksort, which input order guarantees Θ(n²) work?

  1. every randomly shuffled input
  2. already sorted input
  3. every input with distinct keys
  4. only arrays of fixed small size

Answer: option B. Every pivot is then an extreme element and one side of the partition is empty.

Question 7 · easy

Which is the strongest valid lower bound listed for worst-case comparison sorting of n distinct keys?

  1. Ω(n)
  2. Ω(n log n)
  3. Ω(n²)
  4. Ω(log n)

Answer: option B. The decision tree needs n! leaves, so height at least lg(n!).

Question 8 · easy

Which listed sorting method naturally supports an external-memory implementation using sequential runs and merges?

  1. quicksort
  2. heapsort
  3. mergesort
  4. insertion sort

Answer: option C. It streams data sequentially, which suits disks.

Question 9 · easy

In least-significant-digit-first radix sort, each digit pass must be:

  1. stable
  2. recursive
  3. in place
  4. randomised

Answer: option A. Ties on the current digit must keep the order established by earlier passes.

Question 10 · easy

What is the tightest listed upper bound for building a binary heap using bottom-up heapify?

  1. O(n)
  2. O(n log n)
  3. O(n²)
  4. O(log n)

Answer: option A. Most nodes are near the bottom and cost almost nothing to bubble down.

Question 11 · medium

The best-case running time of insertion sort is:

  1. Θ(n)
  2. Θ(n log n)
  3. Θ(n²)
  4. Θ(1)

Answer: option A. On already sorted input, each outer iteration performs a constant amount of work and no shifting. There are n − 1 such iterations, giving Θ(n). The inner condition is still checked.

Question 12 · medium

Insert 1 into the min-heap [2, 4, 3]. The final array is:

  1. [2, 4, 3, 1]
  2. [1, 2, 3, 4]
  3. [1, 4, 3, 2]
  4. [1, 3, 2, 4]

Answer: option B. 1 lands at position 4 under 4, swaps up to position 2, then swaps with the root 2.

Question 13 · medium

Extract the minimum from the min-heap [1, 3, 2, 7, 4]. The remaining heap is:

  1. [2, 3, 4, 7]
  2. [3, 2, 4, 7]
  3. [2, 4, 3, 7]
  4. [3, 7, 2, 4]

Answer: option A. The last element 4 moves to the root, then swaps with its smaller child 2.

Question 14 · medium

Apply Lomuto partition to [4, 9, 1, 7, 3]: scan left to right, move keys strictly below the last pivot 3 into the next low slot, then swap the pivot into that slot. What is the result?

  1. [1, 3, 4, 7, 9]
  2. [1, 3, 9, 4, 7]
  3. [3, 1, 4, 7, 9]
  4. [1, 9, 4, 7, 3]

Answer: option A. Only 1 is smaller than the pivot; it is swapped to the front, then the pivot is swapped into position 1, giving [1, 3, 4, 7, 9].

Question 15 · medium

In the worst case over two nonempty sorted lists with 10 items in total, how many key comparisons does the standard merge need?

  1. 5
  2. 9
  3. 10
  4. 45

Answer: option B. n − 1: the last element is copied without a comparison.

Question 16 · medium

For n distinct keys and uniformly random pivots, the leading term of quicksort’s expected comparison count is:

  1. n²/2
  2. 1.39 n lg n
  3. n
  4. 2ⁿ

Answer: option B. The exact expectation is 2(n + 1)Hₙ − 4n. Its leading term is 2n ln n = (2 ln 2)n lg n ≈ 1.386n lg n; lower-order terms are omitted.

Question 17 · medium

The median-of-three pivot rule takes:

  1. the mean of three values
  2. the median of the first, middle and last elements
  3. a random element
  4. the last element

Answer: option B. The median is an actual element and is not dragged around by one extreme value.

Question 18 · medium

Using Θ(n) buckets and insertion sort within each bucket, which distribution assumption gives expected O(n) bucket-sort time?

  1. all keys enter one bucket in arbitrary order
  2. keys are independent and uniform over a known fixed interval
  3. keys arrive already sorted but all enter one bucket
  4. no assumption is needed

Answer: option B. Independent uniform keys give bounded expected bucket occupancy and O(n) expected total local-sorting work. It is not a worst-case linear guarantee for arbitrary keys.

Question 19 · medium

Radix sort is run on 170, 45, 75, 90, 802, 24. After the first pass (on the units digit) the order is:

  1. 170, 90, 802, 24, 45, 75
  2. 24, 45, 75, 90, 170, 802
  3. 90, 170, 802, 24, 45, 75
  4. 802, 24, 45, 75, 170, 90

Answer: option A. Units digits 0, 0, 2, 4, 5, 5; the stable pass keeps 170 before 90 and 45 before 75.

Question 20 · hard

For n ≥ 2, sort n integers in [0, n³ − 1] using word-RAM radix sort in base n. How many stable counting-sort passes suffice for O(n) total time?

  1. 1 pass
  2. 2 passes
  3. 3 passes
  4. log n passes

In simpler words: Count digits in base n instead of base ten.

Starting hint: The biggest allowed integer is just below n³.

Answer: option C. Each number has three base-n digits, and each pass is a linear-time stable bucket sort.

Step by step
  1. Write x=d₂n²+d₁n+d₀, with each digit in 0,…,n−1.
  2. Three stable counting-sort passes handle d₀, d₁, d₂. Each costs O(n+n), so the total is O(n).

Written questions

Read each question together with its explanation, trace or proof. Numbering continues from the test questions.

Question 21 · easy

Is the array [3, 5, 4, 10, 8, 7] (positions 1 to 6) a valid min-heap?

Answer & reasoning

yes. Position 1 (3) has children 5 and 4; position 2 (5) has children 10 and 8; position 3 (4) has child 7. Every parent is ≤ its children.

Question 22 · easy

In the array layout of a heap, where are the children of position 6, and where is the parent of position 13?

Answer & reasoning

children at 12 and 13; parent of 13 is ⌊13/2⌋ = 6.

Question 23 · easy

What sits at the root of a max-heap, and where could the smallest element be?

Answer & reasoning

The root holds a largest key. With distinct keys, a smallest key must be a leaf and can be at any leaf. If duplicates are allowed, a minimum can also occur at an internal node; for example, an all-equal heap.

Question 24 · easy

Insert 2 into the min-heap [3, 5, 4, 10, 8, 7]. Show the bubble-up steps and the final array.

Answer & reasoning

append 2 at position 7 (child of position 3, which holds 4). 4 > 2, swap: [3, 5, 2, 10, 8, 7, 4]. Its parent is now position 1 (3); 3 > 2, swap: [2, 5, 3, 10, 8, 7, 4]. At the root, stop.

Question 25 · easy

Extract the minimum from [2, 5, 3, 10, 8, 7, 4]. Show the steps and the resulting heap.

Answer & reasoning

remove 2, move the last element 4 to the root: [4, 5, 3, 10, 8, 7]. Children of 4 are 5 and 3; the smaller, 3, is smaller than 4, so swap: [3, 5, 4, 10, 8, 7]. Position 3 (4) now has child 7 only; 7 > 4, stop.

Question 26 · easy

Write the recurrence for mergesort’s running time and its solution.

Answer & reasoning

T(n) = 2T(n/2) + Θ(n), so T(n) = Θ(n log n): linear merging on each of lg n levels.

Question 27 · easy

Merge [1, 4, 9] and [2, 3, 10]. Give the output and count the comparisons.

Answer & reasoning

1, 2, 3, 4, 9, 10. Comparisons: 1 vs 2, 4 vs 2, 4 vs 3, 4 vs 10, 9 vs 10; five comparisons, then 10 is copied with none. That is n − 1 = 5 for n = 6.

Question 28 · easy

What input makes quicksort with the last element as pivot take Θ(n²)?

Answer & reasoning

an already sorted (or reverse sorted) array: every pivot is the largest or smallest element, so one side of every partition is empty.

Question 29 · easy

Bucketsort can run in O(n). Why does that not contradict the Ω(n log n) lower bound?

Answer & reasoning

the bound applies to comparison-based sorting only. Bucketsort uses the numeric value of a key to pick its bucket directly, which is not a comparison, and it relies on an assumption about the distribution of the keys.

Question 30 · easy

Which O(n log n) sort is preferred when the data does not fit in memory, and why?

Answer & reasoning

mergesort, because it reads and writes data in long sequential streams, which is what disks do well, instead of jumping around.

Question 31 · easy

What two operations does heapsort consist of, and what does each cost?

Answer & reasoning

build a heap from all n items once (O(n) with heapify), then extract the minimum n times (O(log n) each). Total O(n log n).

Question 32 · medium

Compare the best-case running times of selection sort and insertion sort and explain the difference.

Answer & reasoning

selection sort is Θ(n²) even in the best case, because it scans the whole remaining array to find each minimum regardless of the input. Insertion sort is Θ(n) on an already-sorted input, because its inner while-loop stops immediately for every item.

Question 33 · medium

Describe two ways to sort n numbers with a balanced BST, and their cost.

Answer & reasoning

Insert all records into a balanced BST in O(n log n), keeping a multiplicity count or list for duplicate keys. Then an in-order traversal outputs all n records in O(n). Alternatively, repeatedly find and delete a minimum, costing O(n log n) overall. A set-like tree that silently discards duplicates would not correctly sort the original sequence.

Question 34 · medium

Partition the array [8, 3, 6, 1, 9, 2, 5] around the pivot 5 (the last element) using the partition routine from Lecture 8. Show the array after each swap and the pivot’s final index.

Use zero-based Lomuto partitioning: scan all items before the last pivot, swapping each item strictly less than the pivot into the next low slot, then swap the pivot into that slot.

Answer & reasoning

firsthigh starts at index 0. 8 stays. 3 < 5: swap with index 0 → [3, 8, 6, 1, 9, 2, 5], firsthigh 1. 6 stays. 1 < 5: swap with index 1 → [3, 1, 6, 8, 9, 2, 5], firsthigh 2. 9 stays. 2 < 5: swap with index 2 → [3, 1, 2, 8, 9, 6, 5], firsthigh 3. Finally swap the pivot into index 3 → [3, 1, 2, 5, 9, 6, 8]. Everything left of 5 is smaller and everything right is larger.

Question 35 · medium

Turn [9, 4, 7, 1, 3, 8, 2] into a min-heap with the linear-time heapify (bubble down positions 3, 2, 1 in that order). Show the array after each position.

Answer & reasoning

position 3 holds 7 with children 8 and 2; swap with 2 → [9, 4, 2, 1, 3, 8, 7]. Position 2 holds 4 with children 1 and 3; swap with 1 → [9, 1, 2, 4, 3, 8, 7]. Position 1 holds 9 with children 1 and 2; swap with 1 → [1, 9, 2, 4, 3, 8, 7]; 9 now at position 2 has children 4 and 3; swap with 3 → [1, 3, 2, 4, 9, 8, 7]. Done, and every parent is ≤ its children.

Question 36 · medium

Each bubble-down can cost O(log n), and heapify calls it n/2 times. Why is heapify O(n) rather than O(n log n)?

Answer & reasoning

the cost of a bubble-down is the height of the node, not log n. Half the nodes are leaves (height 0, cost nothing), a quarter have height 1, an eighth height 2, and so on. The total is n × Σ h/2ʰ⁺¹, and Σ h/2ʰ converges to 2, so the total is at most about 2n.

Question 37 · medium

Why is the guarantee of randomised quicksort stronger than the statement “quicksort runs in Θ(n log n) on random inputs”?

Answer & reasoning

For distinct keys, random pivots give expected Θ(n log n) work for every fixed input, with expectation over the algorithm’s random choices. This does not require the input itself to be random. The worst case remains Θ(n²). With many duplicates, a two-way partition can still be quadratic even with random pivots; use a three-way partition and analyse that implementation separately.

Question 38 · medium

When choosing a pivot as the “median of three” (first, middle, last), why take the median rather than the mean of the three values?

Answer & reasoning

the median is one of the actual elements, so it can be swapped into place and it splits the values around it. The mean may not be an element at all, and one extreme value drags it far from the middle of the data.

Question 39 · medium

Prove that merging two sorted lists with n elements in total needs at most n − 1 comparisons.

Answer & reasoning

every comparison moves exactly one element to the output. Once one list is empty, the rest of the other is copied without comparisons, so at least the last element costs nothing; therefore at most n − 1 comparisons occur.

Question 40 · medium

Buckets numbered 1–10 cover 1–10, 11–20, …, 91–100. Which bucket contains 37? What happens if all ten values lie between 91 and 100?

Answer & reasoning

37 goes into bucket 4. Values 91–100 all go into bucket 10. Insertion-sorting one crowded bucket can take Θ(n²) work in the worst case. Expected linear bucket sorting needs an appropriate distribution assumption and a linear number of buckets; it is not a guarantee for arbitrary inputs.

Question 41 · medium

Radix-sort 329, 457, 657, 839, 436, 720, 355 by units, then tens, then hundreds. Show the order after each pass.

Answer & reasoning

after the units pass (stable): 720, 355, 436, 457, 657, 329, 839. After the tens pass: 720, 329, 436, 839, 355, 457, 657. After the hundreds pass: 329, 355, 436, 457, 657, 720, 839. Each pass must be stable so earlier passes break ties.

Question 42 · medium

How many comparisons does any algorithm need in the worst case to sort 3 items? Can that bound be achieved?

Answer & reasoning

the decision tree needs at least 3! = 6 leaves, and a tree of height 2 has at most 4, so some input needs at least 3 comparisons. Three do suffice: compare a and b, compare the larger with c, and one more comparison places the remaining element.

Question 43 · hard

Show that no comparison-based dictionary can support both insert and delete-minimum in o(log n) worst-case time each.

In simpler words: Use a hypothetical faster dictionary to build an impossibly fast sort.

Starting hint: Insert everything, then repeatedly remove the smallest.

Answer & reasoning
Step by step
  1. Little-o(log n) means a cost whose ratio to log n tends to zero, not just a small constant factor.
  2. If both operations had that worst-case cost, n insertions and n removals would use o(n log n) comparisons.
  3. The removals print sorted order. This contradicts the comparison-sorting lower bound, so the two assumed bounds cannot both hold.

Otherwise, insert n distinct keys and delete the minimum n times to sort them using o(n log n) comparisons in total. This contradicts the comparison-sorting lower bound. Thus both operations cannot simultaneously have o(log n) worst-case cost. The claim concerns this pair of operations, not every dictionary operation individually.

Question 44 · hard

Prove that lg(n!) = Θ(n log n).

In simpler words: Trap the logarithm of n! between two n log n expressions.

Starting hint: For the lower bound, keep only the largest half of the factors.

Answer & reasoning
Step by step
  1. Upper bound: each of the n factors is at most n, so n! ≤ nⁿ.
  2. Lower bound: at least n/2 factors are at least n/2, so n! ≥ (n/2)^(n/2), ignoring harmless integer rounding.
  3. Taking logs gives (n/2)log₂(n/2) ≤ log₂(n!) ≤ n log₂ n. Both sides grow as n log n.

upper bound: n! ≤ nⁿ, so lg(n!) ≤ n lg n. Lower bound: the largest n/2 factors of n! are each at least n/2, so n! ≥ (n/2)^(n/2) and lg(n!) ≥ (n/2) lg(n/2) = (n/2)(lg n − 1), which is Ω(n log n). Together, Θ(n log n).

Question 45 · hard

Sort n integers, each between 0 and n² − 1, in O(n) time.

In simpler words: Sort bounded integers using two digits instead of pairwise comparisons.

Starting hint: Write x as high·n + low.

Answer & reasoning
Step by step
  1. For 0 ≤ x < n², high = floor(x/n) and low = x mod n, each in 0,…,n−1.
  2. Stable counting sort first by low, then by high. Stability preserves the low-digit order within a high-digit tie.
  3. Each pass scans n items and n counters: O(n). Two passes remain O(n), assuming the integers fit in a constant number of machine words.

write each number in base n; it has exactly two digits, each between 0 and n − 1. Radix sort with two passes, each a stable bucket sort into n buckets, costs O(n) per pass. Comparison sorting would need Ω(n log n); the trick is that the keys are bounded.

Question 46 · hard

Explain how heapsort sorts an array into ascending order in place, without a second array.

In simpler words: Use the unused end of the same array as the sorted output.

Starting hint: A max-heap already puts the largest remaining item at its root.

Answer & reasoning
Step by step
  1. Build a max-heap in the array.
  2. Swap its root with the last active slot; that slot now contains its final sorted value.
  3. Shorten the active heap, then bubble the new root down. Repeat; the sorted suffix grows and needs no second array.

build a max-heap inside the array. The largest item is at position 1; swap it with the last item, shrink the heap by one, and bubble the new root down. Repeat. Each round moves the current maximum into the final, still-unsorted position at the end, so the array fills with sorted items from the back.

Question 47 · hard

Numbers arrive one at a time. Design a structure that reports the current median after each arrival in O(log n) per number.

In simpler words: Keep the middle values at the tops of two heaps.

Starting hint: Separate the smaller half from the larger half.

Answer & reasoning
Step by step
  1. The smaller half is a max-heap, so its largest item is visible. The larger half is a min-heap, so its smallest is visible.
  2. After insertion, move a root across if the sizes differ by more than one. Keep every lower-half value ≤ every upper-half value.
  3. For odd size, report the larger heap’s root. For even size, report the mean of both roots. Each insertion needs only a constant number of O(log n) heap operations.

keep a max-heap of the smaller half and a min-heap of the larger half, with sizes differing by at most one. Insert into the appropriate heap, then move one root across if the sizes get out of balance. The median is the root of the bigger heap (or the average of the two roots when sizes are equal). Each step is a constant number of heap operations.

Question 48 · hard

Merge k nonempty sorted lists containing n elements in total, for 2 ≤ k ≤ n, in O(n log k) time.

In simpler words: Repeatedly choose the smallest of the current list heads.

Starting hint: Only one candidate from each list needs to be in the heap.

Answer & reasoning
Step by step
  1. Put the first item of each nonempty list into a min-heap, remembering its list.
  2. Remove the smallest, output it, then add the next item from the same list.
  3. The heap never exceeds k entries. Each of n outputs costs O(log k); bottom-up heap construction costs O(k).

put the first element of each list into a min-heap of size k. Repeatedly extract the minimum, append it to the output, and insert the next element from the list it came from. Each of the n elements passes through the heap once at O(log k).

Question 49 · hard

Prove that any algorithm that sorts by swapping only adjacent elements (insertion sort, bubble sort) needs Ω(n²) swaps in the worst case.

In simpler words: Measure how many out-of-order pairs an adjacent swap can fix.

Starting hint: Start with a reverse-sorted array of distinct keys.

Answer & reasoning
Step by step
  1. An inversion is a pair of positions i < j whose values satisfy a[i] > a[j].
  2. Reverse order contains n(n−1)/2 inversions.
  3. Swapping neighbours changes only their mutual order, removing at most one inversion. Reaching zero therefore needs Ω(n²) swaps in this case.

call a pair of elements in the wrong order an inversion. A reverse-sorted array has n(n − 1)/2 inversions. Swapping two adjacent elements changes the order of only that pair, so it removes at most one inversion. Hence at least n(n − 1)/2 = Ω(n²) swaps are needed on that input.

Question 50 · hard

Run quicksort with the partition routine of Lecture 8 on an array where all n keys are equal. What happens, and how would you fix it?

Use the two-way partition described in Exercise 77: only values strictly less than the last-element pivot enter the low partition.

In simpler words: Trace what happens when the partition never finds a smaller key.

Starting hint: With all keys equal, every strict “less than pivot” test fails.

Answer & reasoning
Step by step
  1. The pivot moves to one end and the remaining subproblem has n−1 keys.
  2. Work is proportional to n+(n−1)+…+1, so it is quadratic.
  3. Three-way partition collects equal keys into a middle block. No recursion is needed on that block; all-equal data is handled in one linear scan.

no element is strictly less than the pivot, so every element stays on the “high” side; each partition removes only the pivot and the recursion depth becomes n, giving Θ(n²). Fix: a three-way partition into “less than”, “equal to” and “greater than” the pivot, and recurse only on the outer two parts; the all-equal case then finishes in O(n).

Three core tasks

Predict on paper, run the code, then explain any difference. Use the animations below to inspect individual steps.

1. Trace

Draw the first bubble pass on [5, 1, 4, 2, 8]. Mark every swap.

Check your reasoning

5 swaps with 1, then 4, then 2; no swap with 8. Result [1, 4, 2, 5, 8].

2. Calculate

How many comparisons does selection sort make for n = 8?

Check your reasoning

8 × 7 / 2 = 28, even if the input is already sorted.

3. Change one thing

Reverse the order of Ada and Sam in the input. Sort by score again.

Check your reasoning

Sam now stays before Ada among the equal score-80 records. Stability preserves input order for ties.

Explore the animations & more worked tasks

13.9Try it yourself

Task 1 — on paper first

Sort [5, 1, 4, 2, 8] by hand with bubble sort, writing out the list after each pass, and count comparisons and swaps. Then run the code and check that your numbers match its output exactly (9 comparisons, 4 swaps).

Animate it — check your paper trace, or be the machine
Task 2 — confirm the class

Run bubble_sort and selection_sort at n = 500, 1 000, 2 000, 4 000 on random data. Record comparisons and seconds for each, and compute the ratio column for both.

Animate it — double n and watch the ratio column
Expected

Selection comparisons follow n(n−1)/2, whose doubling ratio approaches four rather than equalling it exactly. Bubble comparisons also depend on early exit. Times may approximately quadruple on comparable difficult inputs. Selection sort usually wins slightly on time despite identical comparison counts, because it does far fewer swaps — a constant-factor difference within the same class.

Task 3 — best and worst case

Run bubble sort on (a) already sorted data, (b) reverse-sorted data, (c) random data, at n = 2 000. Explain the three comparison counts.

Animate it — sorted, reversed and random, side by side
Expected

(a) about 2 000 — one clean pass, then the early exit fires: O(n). (b) about 2 million — every comparison and every swap: the worst case. (c) roughly the worst case too, because a random list needs nearly all the passes. Selection sort shows no such variation at all.

Task 4 — the honest comparison plot

Plot bubble sort, selection sort, insertion sort and sorted() on one log–log figure across four sizes. Report the slope of each line in words, and state the largest n you would be willing to hand each one.

Animate it — build the log–log plot one size at a time
Task 5 — insertion sort loves order

Run insertion_sort on (a) already-sorted, (b) reverse-sorted, and (c) random data at n = 2 000, reporting comparisons for each. Which input is its best case, and why is the reverse-sorted input its worst?

Animate it — watch each card slide into place
Expected

(a) about 1 999 — every item is already in place, so each inner while stops after a single comparison: O(n), its best case. (b) about 2 million — every item must travel all the way to the front, shifting everything: the worst case, O(n²). (c) roughly half the worst case. This sensitivity to how sorted the input already is is exactly why Timsort reaches for insertion sort on short, nearly-ordered runs.

Task 6 — stability you can see

Build a list of (name, grade) tuples where several people share a grade. Sort it by grade with sorted(..., key=lambda p: p[1]) and confirm that same-grade people keep their input order. Then sort by (grade, name) and describe, in one sentence, what changed and why.

Animate it — watch the ties keep their order
Expected

With the single key, ties keep input order (that is stability). With the tuple key, ties are now broken by name alphabetically, because the second element of the tuple is consulted whenever the first is equal. Same sort, richer key.

Check your understanding

13.10Self-check

Bubble sort on 4 000 random items does about 8 million comparisons. At 8 000 items, expect about:

Quadratic dominant growth: doubling n approximately quadruples the full-pass comparison count; the exact count is n(n−1)/2.

Where does the "log n" in n log n come from?

Split, sort halves, merge: log n levels of splitting, each doing O(n) merging work.

data = data.sort() leaves data holding:

Use data.sort() alone, or data = sorted(data). This bug appears in every beginner cohort.

Bubble sort and selection sort do the same number of comparisons. Why is selection sort often faster in practice?

Same class, different constant. This is exactly why we report both the class and the measurement.

In the doubling table, sorted()'s time multiplies by about 2.1 each time n doubles. That ratio is the fingerprint of:

A pure O(n) line would double (2.0×); O(n²) would quadruple (4×). Just above 2 is the signature of n log n.

A stable sort guarantees that:

Stability is about ties, not speed. It is what lets you sort by several keys in stages, each pass preserving the last.
Extra material & reference
Optional depth · full technical reference

13.1Why study slow sorts?

You will never ship bubble sort. You study it because it is the clearest example in all of computing of a genuine trade: two methods, both obviously correct, separated by a complexity class you can feel on a laptop within thirty seconds.

Sorting also underpins week 12 (binary search needs sorted data), week 9 (the sort-and- compare anagram solution) and any report you will ever produce from data.

13.2Bubble sort

Walk along the row comparing neighbours; swap them if they are out of order. Each full pass drags the largest remaining value to the end — it "bubbles up". Repeat until a pass makes no swaps.

bubble_sort.py
def bubble_sort(data):
    """Sorts a copy of data. Returns (sorted list, comparisons, swaps)."""
    items = data[:]                      # work on a copy
    comparisons = swaps = 0
    n = len(items)

    for end in range(n - 1, 0, -1):      # shrinking unsorted region
        swapped = False
        for i in range(end):
            comparisons += 1
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swaps += 1
                swapped = True
        if not swapped:                  # already sorted — stop early
            break

    return items, comparisons, swaps

print(bubble_sort([5, 1, 4, 2, 8]))
([1, 2, 4, 5, 8], 9, 4)

Worst-case cost. When all passes are needed, their lengths sum to (n−1) + (n−2) + … + 1 = n(n−1)/2 comparisons — O(n²). The early exit gives a best case of O(n) on data that is already sorted, which is bubble sort's only redeeming feature. (Here the early exit fires after the third pass finds nothing to swap, so it stops at 9 comparisons instead of the full 10.)

13.3Selection sort

Find the smallest item, put it first. Find the smallest of the rest, put it second. Continue. This is what most people do with a hand of cards.

selection_sort.py
def selection_sort(data):
    items = data[:]
    comparisons = swaps = 0

    for start in range(len(items)):
        smallest = start
        for i in range(start + 1, len(items)):
            comparisons += 1
            if items[i] < items[smallest]:
                smallest = i
        if smallest != start:
            items[start], items[smallest] = items[smallest], items[start]
            swaps += 1

    return items, comparisons, swaps

Same n(n−1)/2 comparisons — O(n²) in every case, best included, because it cannot know it is finished early. But it performs at most n−1 swaps, against bubble sort's possible n²/2. If moving items is expensive and comparing them is cheap, that matters. Two algorithms in the same class can still differ in ways worth measuring.

13.4Insertion sort, and all three by hand

The third classic completes the set. Take each item and slide it back into its correct place among the already-sorted items on its left — the way most people order a hand of playing cards as they pick them up.

insertion_sort.py
def insertion_sort(data):
    items = data[:]
    comparisons = shifts = 0

    for i in range(1, len(items)):
        current = items[i]               # the card in your hand
        j = i - 1
        while j >= 0:
            comparisons += 1
            if items[j] > current:       # make room by shifting right
                items[j + 1] = items[j]
                shifts += 1
                j -= 1
            else:
                break
        items[j + 1] = current           # drop it into the gap

    return items, comparisons, shifts

print(insertion_sort([5, 1, 4, 2, 8]))
([1, 2, 4, 5, 8], 7, 4)

Insertion sort is O(n²) in the worst case, but genuinely fast on nearly-sorted data — on an already-sorted list every item drops straight in after a single comparison, giving O(n). That is why real sorting libraries use it for small chunks.

Now the point of this section: sort [5, 1, 4, 2, 8] by hand with each method, writing the list after every pass, and confirm your counts against the three outputs above.

Bubble — after each passSelection — after each roundInsertion — after each insert
start [5,1,4,2,8]start [5,1,4,2,8]start [5,1,4,2,8]
pass 1 → [1,4,2,5,8]put smallest first → [1,5,4,2,8]insert 1 → [1,5,4,2,8]
pass 2 → [1,2,4,5,8]next smallest → [1,2,4,5,8]insert 4 → [1,4,5,2,8]
pass 3 → no swaps, stoprest already in placeinsert 2 → [1,2,4,5,8]; insert 8 → done
9 comparisons, 4 swaps10 comparisons, 2 swaps7 comparisons, 4 shifts

Three correct answers, three different amounts of work on the very same five numbers. Each function begins with data[:], so these copy-returning implementations require O(n) extra space. Their in-place sorting cores need only O(1) extra storage. Selection sort always does its full 10 comparisons; bubble sort's early exit saves it one; insertion sort does the fewest here because the data was not badly scrambled. The class is the same for all three — the constants are not.

13.5Where n log n comes from

All three sorts above compare, in the worst case, every item with essentially every other. The better sorts refuse to do that, using a divide-and-conquer idea:

  1. Split the list into two halves.
  2. Sort each half (by the same method, on smaller pieces).
  3. Merge the two sorted halves by repeatedly taking the smaller front item — one pass, O(n).

How many times can you split a list of n items in half? log n times — the same halving from weeks 1 and 12. Each of those levels does O(n) work merging. So the total is n × log n.

nn² growth unitsn log₂ n growth unitsHow much better
10010 00066415×
1 0001 000 0009 966100×
10 000100 000 000132 877753×
1 000 00010¹²19 931 56950 000×

You will not implement merge sort in this course — writing it well needs recursion, which belongs to the follow-on course. What you need is the intuition ("split, sort, merge — log n levels of n work each") and the ability to recognise its 2.1–2.2 ratio in a doubling experiment.

13.6Python's sorted(), and how far ahead it is

your sort vs the real one
import time, random

for n in [1000, 2000, 4000, 8000]:
    data = [random.randrange(1000000) for _ in range(n)]

    start = time.perf_counter()
    result_b, comps, swaps = bubble_sort(data)
    t_bubble = time.perf_counter() - start

    start = time.perf_counter()
    result_p = sorted(data)
    t_python = time.perf_counter() - start

    print(f"n={n:>5}  bubble {t_bubble:8.4f}s ({comps:,} comparisons)"
          f"   sorted() {t_python:.5f}s   {t_bubble/t_python:,.0f}x")
    assert result_b == result_p          # both are correct!
n= 1000 bubble 0.0921s (499,500 comparisons) sorted() 0.00023s 401x n= 2000 bubble 0.3701s (1,999,000 comparisons) sorted() 0.00048s 771x n= 4000 bubble 1.4890s (7,998,000 comparisons) sorted() 0.00104s 1,432x n= 8000 bubble 5.9612s (31,996,000 comparisons) sorted() 0.00228s 2,615x

The assert line matters: both produce identical output. The difference is entirely in how the answer is reached. Read the two time columns down the page as a doubling experiment, exactly as in weeks 5–7:

n doublesbubble time × …sorted() time × …what the ratio says
1000 → 20000.37 / 0.09 ≈ 4.0×0.00048 / 0.00023 ≈ 2.1×4× is n²; 2.1× is n log n
2000 → 40001.49 / 0.37 ≈ 4.0×0.00104 / 0.00048 ≈ 2.2×same story, one class down
4000 → 80005.96 / 1.49 ≈ 4.0×0.00228 / 0.00104 ≈ 2.2×and it holds every row

A near-four doubling ratio supports quadratic growth; a ratio a little above two can support n log n over this range. Ratios are evidence to compare with operation counts, not a proof by themselves. The illustrative measurements suggest a growing speedup. Extrapolating the displayed bubble time to n = 100 000 gives about 5 000 million comparisons and roughly fifteen minutes under the same model; actual timings, especially for adaptive built-in sorting, must be measured on the stated workload.

What Python actually uses

An algorithm called Timsort: merge sort combined with insertion sort for small runs, plus a trick that detects stretches of data that are already in order. It is O(n log n) in the worst case and O(n) on already-sorted data — and it is written in C. That is your baseline. Beating it is a research project, not routine practice.

13.7Using sorting properly

the everyday toolkit
data = [5, 2, 9, 1]

new = sorted(data)              # returns a new list, leaves data alone
data.sort()                     # sorts in place, returns None

names = ["Cem", "ada", "Bilal"]
print(sorted(names))                          # capitals first — probably not what you want
print(sorted(names, key=str.lower))           # case-insensitive

students = [("Ada", 88), ("Bilal", 72), ("Cem", 91)]
print(sorted(students, key=lambda s: s[1], reverse=True))   # by grade, best first
The classic beginner bug

data = data.sort() throws your list away and leaves you holding None. Use data.sort() on its own line, or data = sorted(data) — never both at once.

One more cost worth knowing: sorting inside a loop is a classic accidental disaster. Sorting a list of n items m times is O(m · n log n) when sorting once outside the loop would have done. Ask yourself every time: does this need to happen again?

13.8Stability, and sorting by more than one key

A sort is stable when items that compare equal keep their original order. Python's sorted and list.sort are stable — a guarantee, not an accident — and it is more useful than it first sounds.

equal keys keep their order
scores = [("Ada", 88), ("Bilal", 88), ("Cem", 72)]

print(sorted(scores, key=lambda p: p[1], reverse=True))
[('Ada', 88), ('Bilal', 88), ('Cem', 72)]

Ada and Bilal both scored 88, and Ada stays ahead of Bilal because she came first in the input. An unstable sort would be free to swap them, and you would have no way to predict the order of ties.

Stability is what lets you sort by several keys in stages: sort by the least important key first, then by the most important, and the earlier order survives inside each group. Or, more directly, hand key a tuple and let Python compare left to right:

two keys at once
students = [
    ("maths",   "Bilal"),
    ("art",     "Cem"),
    ("maths",   "Ada"),
    ("art",     "Ada"),
]

# by subject A→Z, then by name A→Z within each subject
print(sorted(students, key=lambda s: (s[0], s[1])))
[('art', 'Ada'), ('art', 'Cem'), ('maths', 'Ada'), ('maths', 'Bilal')]

The tuple (subject, name) is compared position by position: subjects first, and names only to break a tie on subject. To mix directions — say subject ascending but grade descending — sort in two stable passes (grade first with reverse=True, then subject). For numeric grades, a single tuple key such as (subject, -grade) also expresses subject ascending and grade descending.

From the beginner notes · Lectures 3, 7, 8, 9

Merge first, then explain the full sort

Merging two sorted lists only compares their next items that have not yet been copied. Each comparison chooses one item to copy to the result. When one list empties, copy the rest without more key comparisons. With n items in total, at most n − 1 comparisons are needed when both lists start nonempty.

Mergesort merges all n items at each level, across about log₂ n levels. Quicksort splits items around a chosen value, called the pivot, instead: choosing pivots randomly gives expected O(n log n) comparisons in the usual analysis, but repeatedly splitting into very unequal parts can be quadratic. Equal values need care. Three-way partitioning makes separate groups smaller than, equal to and larger than the pivot.

The lower bound for sorts based only on comparisons does not apply to every kind of sort. Counting sort uses counts within a known value range; radix sort groups values by digits. Check the key range, whether equal-value records must keep their original order and memory cost before claiming a faster solution.

Engineering use. Merge timestamped sensor streams and keep equal-time records in a defined order.

Learning goals & class plan
By the end of this week you can
  • perform bubble, selection and insertion sort by hand on paper;
  • implement all three, count their comparisons and swaps, and confirm the n² pattern;
  • explain in plain words where n log n comes from, and see it beat n² in a measured table;
  • measure the gap between your sort and Python's sorted();
  • use sort, sorted and key= properly, and explain what a stable sort buys you.
Three-hour interactive studio

00:00–01:00: launch, predict–run–explain cycle, questions  ·  01:00–01:10: break  ·  01:10–02:00: worked variation, peer instruction, questions  ·  02:00–02:10: break  ·  02:10–03:00: core mechatronics practice, exam bridge, and exit ticket.

Ask at any point. Weekly self-checks stay private; optional extensions are not collected.

Need a slower explanation? Open the English + Türkçe reference guide.

Optional extra practice

13.11Optional Studio Extension

Optional practice · no submission or deadline
  1. Create AA_Week13.ipynb and complete Tasks 1–6.
  2. Add insertion sort's comparison counts to the Task 4 figure so all three hand-written sorts and sorted() appear together.
  3. Reproduce the doubling table from §13.6 with your own timings, and state the ratio each algorithm settles on. Compare the observed ratios with the operation analysis and state the input case; ratios alone do not prove the class.
  4. Write the five-sentence interpretation for the Task 4 figure, including a prediction of bubble sort's runtime at n = 50 000 (do not run it — say how you extrapolated from the 4× ratio).
  5. Bring a working draft of your final project: both approaches implemented, at least one benchmark table produced. Week 14 is a workshop.
Optional reference · Words from this week

13.12Words from this week

TermMeaning in plain words
bubble sortRepeatedly swap out-of-order neighbours. O(n²), O(n) on sorted data.
selection sortRepeatedly pick the smallest remaining item. O(n²) always, few swaps.
insertion sortSlide each item back into its place. O(n²) worst, O(n) on already-sorted data.
divide and conquerSplit the problem, solve the parts, combine — the source of log n levels.
mergeCombine two sorted lists into one in a single pass.
TimsortPython's built-in sort: O(n log n) worst case, O(n) on already-ordered data.
stable sortOne that keeps equal items in their original order — lets you sort by keys in stages.
in placeModifies the original container. This does not promise constant workspace: Python list sorting may use O(n) extra memory.
Chapter problem set — Skiena 2.10

13.13Chapter problem set — Skiena 2.10

Sorting rested on a summation — adding up n(n−1)/2 comparisons — so this is a good week to practise reading a pattern and pinning down the expression behind it. Here is one of Skiena's, solved the way this course likes: spot the pattern, then say why.

Problem 2-33 · a self-referential triangle

Build a triangle in which every entry is the sum of the three entries directly above it (above-left, above, above-right — treat any missing neighbour as 0). It begins:

rowentries
11
21  1  1
31  2  3  2  1
41  3  6  7  6  3  1

Find an expression for the sum of the entries in the i-th row, and justify it.

Worked solution

Add up each row first and look for the pattern: row 1 sums to 1, row 2 to 1+1+1 = 3, row 3 to 1+2+3+2+1 = 9, row 4 to 1+3+6+7+6+3+1 = 27. That is 1, 3, 9, 27 — the powers of three. So the answer looks like 3i−1.

Now the why, which is the pretty part. Ask where each entry's value ends up in the next row down. An entry sitting in one row is one of the "three above" for exactly three positions in the row beneath it — the slot below-left of it, the slot directly below, and the slot below-right. So every entry contributes its full value to the next row three times over. Add that up across the whole row and you get:

(sum of next row) = 3 × (sum of this row)

The total triples at every step. Row 1 starts at 1, so row i is 1 tripled i−1 times — that is 3i−1. A short program confirms both the rows and their tripling totals:

triangle_rows.py
def next_row(row):
    padded = [0, 0] + row + [0, 0]        # room for the row widening by one each side
    return [padded[i] + padded[i + 1] + padded[i + 2] for i in range(len(row) + 2)]

row = [1]
for i in range(1, 6):
    print(f"row {i}: sum {sum(row):>3}   {row}")
    row = next_row(row)
row 1: sum 1 [1] row 2: sum 3 [1, 1, 1] row 3: sum 9 [1, 2, 3, 2, 1] row 4: sum 27 [1, 3, 6, 7, 6, 3, 1] row 5: sum 81 [1, 4, 10, 16, 19, 16, 10, 4, 1]

Answer: the i-th row sums to 3i−1, because each entry feeds into three entries below it, so the grand total triples with every new row. The sums 1, 3, 9, 27, 81 are exactly the powers of three, and the reasoning — count how many times each value is reused — is the same "count the contributions" move that gave n(n−1)/2 for the sorts.

Where this leads

You now have the whole toolkit — measuring, naming, choosing, and the cost of the common structures. Week 14 ties it together with a checklist, the classic traps, and your final project.