Essay, code-tracing, bug-fixing and coding questions are in the week's question bank:
Data Structures and Algorithms (DSA27) · Week 10
Advanced sorting (Lecture 10)
These quizzes are for self-study. Your answers are saved on this device only and are not sent anywhere.
-
Which of these is not one of the three steps of divide and conquer?
Comparing every pair is what O(n2) sorts do; divide and conquer is exactly the way to avoid it.
-
The recurrence for the number of steps of merge sort on n elements is:
Two sorts of half the size, plus a merge that touches all n. (a) is binary search; (c) is quicksort's worst case; (d) would be a divide and conquer whose combine step is O(1).
-
_mergemerges two sorted runs of 4 elements each. The largest number of comparisons it can make is:Each comparison sends one element to
scratch, and the last element needs none: at most 4 + 4 - 1 = 7, when the two runs interleave to the end (for example[1, 3, 5, 7]and[2, 4, 6, 8]). -
Merge sort is stable because:
The
<=inif a[i] <= a[j]. With<the sort is still correct but no longer stable (W10-B1). Where it splits (a) has nothing to do with it. -
The extra space merge sort needs, beyond the input, is:
One scratch
Arrayof n slots, shared by every merge, plus an O(log n) call stack — O(n) in total. -
How many calls of
_mergedoesmerge_sortmake on 8 elements?Every merge joins two runs into one; starting from 8 runs of one element, 7 merges leave one run. In general n - 1.
-
merge_sort(list(range(1024)))— already sorted — makes how many comparisons?On sorted input each merge of two runs of m elements empties the left run after m comparisons: n/2 log2 n = 512 × 10 = 5{,}120 (measured). 523,776 (d) is quicksort with
pivot="first"; 1,023 (a) is Timsort. -
During Lomuto's partition, with
jthe next index to look at, the invariant is:The smaller-than-pivot values sit in
a[lo:boundary], the others ina[boundary:j];a[j:hi]is still unknown, so (d) claims too much. -
_partition(a, 0, 7)ona = [6, 3, 9, 1, 8, 2, 7, 4]returns:The pivot is 4; only 3, 1 and 2 are smaller, so it lands at index 3:
[3, 1, 2, 4, 8, 9, 7, 6]. -
How many comparisons with the pivot does one Lomuto partition of a range of 8 elements make?
One comparison per non-pivot element, n - 1 = 7, whatever the order.
-
quick_sort(list(range(n)), pivot="first")makes:Every pivot is the smallest of its range, so each partition peels off one element: (n-1) + (n-2) + … + 1. For n = 1,024 that is 523,776 comparisons, measured.
-
On an already sorted range,
pivot="median3"avoids the worst case because:Of the first, middle and last values of a sorted range, the middle one is the median — the exact middle of the range. Median-of-three does cost comparisons (a), and it is not random (b).
-
Quicksort recurses into the smaller part and loops on the larger. This bounds:
Each recursive call is on at most half of its caller's range, so there are at most log2 n frames. The time is still O(n2) in the worst case (b). On sorted input with
"first"the stack is O(1), but not on every input (d). -
Quicksort is not stable because:
A swap in the partition can move an element past its equal, and nothing puts them back. Recursion (a) and in-place work do not by themselves break stability.
-
In the array layout of a heap, the children of index i are at:
With the root at index 0. (b) is the layout with the root at index 1, used in some textbooks.
-
Build-heap on
[4, 10, 3, 5, 1, 8, 2, 7]gives:The sifts at indices 3, 2, 1, 0 give
[4, 10, 3, 7, 1, 8, 2, 5],[4, 10, 8, 7, 1, 3, 2, 5], unchanged, and[10, 7, 8, 5, 1, 3, 2, 4](W10-T4). A heap is not sorted (a, b). -
Build-heap is O(n), not O(n log n), because:
About n/4 nodes can sink 1 level, n/8 can sink 2, … — the sum n(1/4 + 2/8 + 3/16 + …) is at most n. Measured: about 1.9 n comparisons, the same ratio from n = 1,000 to 8,000.
-
For n = 10, heap sort's build loop sifts down the indices:
From the last parent,
n // 2 - 1 = 4, down to 0. Indices 5 to 9 are leaves. Going up (d) is W10-B2's bug. -
Which sort is O(n log n) in the worst case and needs only O(1) extra space?
Merge sort (a) needs O(n) extra; quicksort (c) is O(n2) in the worst case; insertion sort (d) is O(n2).
-
The lower bound of about n log2 n comparisons applies to:
The argument counts yes/no answers to comparisons. Counting sort (d) never compares and runs in O(n + k).
-
Python's
sorted()andlist.sort()use:Timsort, by Tim Peters (2002): natural runs, insertion sort on short runs, stable merging. Introsort (c) is C++'s
std::sort. -
sorted(list(range(1000)))— already sorted — makes how many comparisons?Timsort finds one ascending run of 1,000 in 999 comparisons and has nothing to merge (measured: 999).
20 marks
Written questions
5 written questions (20 marks). Write your answer first, then open the model answer and its marking points, and mark yourself honestly: each point is worth about one mark.
Written total: 0 / 20
-
Describe merge sort as divide and conquer. Write its recurrence and solve it with a recursion tree. Give its extra space, and explain what makes it stable.
Model answer and marking points
- Divide: split
a[lo:hi]atmid = (lo + hi) // 2— no comparisons. Conquer: sort both halves recursively; a range of 0 or 1 elements is sorted (base case). Combine: merge the two sorted runs with_merge. - Recurrence: T(n) = 2T(n/2) + cn, T(1) = c.
- Recursion tree: the root merges n elements; its two children n/2 each; the four grandchildren n/4 each — every level totals n. The sizes halve, so there are log2 n levels that merge: T(n) = O(n log n), in every case, because the split never depends on the values.
- Space: one scratch
Arrayof n slots, plus log2 n stack frames: O(n). Not in place. - Stable: on a tie,
_mergetakes from the left run (<=), and the left run holds the elements that came first in the input.
- Divide: split
-
Describe Lomuto's partition: what it does, its invariant, and why the pivot is in its final place afterwards. Why is there nothing to "combine" in quicksort?
Model answer and marking points
- Lomuto's partition takes the pivot
a[hi]and one scanj = lo..hi-1. Values smaller than the pivot are swapped to the front, intoa[boundary], andboundarygrows. A final swap puts the pivot ata[boundary]; it returnsboundary. - Invariant:
a[lo:boundary] < pivot <= a[boundary:j]. True at the start (both empty), kept by each step, and at the endj = hi, so every value is on the correct side. - Final place: every value smaller than the pivot is to its left, every other value to its right; sorting either side cannot move any value across, so the pivot's position is its position in the sorted array.
- No combine: after both parts are sorted, left part, pivot, right part is already in order — the partition did the combining in advance. Merge sort is the mirror image: free divide, expensive combine.
- Lomuto's partition takes the pivot
-
Compare the pivot strategies
"first","random"and"median3": the cost of choosing, and the inputs on which each is at its worst. Why is sorted input the case that matters?Model answer and marking points
"first"and"last": O(1) to choose. Worst on sorted and reverse-sorted input: the pivot is the extreme of its range every time, one element per level, n(n-1)/2 comparisons."random": O(1) plus a random number. No fixed input is bad for it: the worst case needs bad luck at almost every level, which is vanishingly unlikely; the expected cost is about 1.39 n log2 n."median3": up to three extra comparisons per partition. Exact middle on sorted and reversed input. Its worst case exists — specially built "median-of-three killer" inputs (Musser, 1997) — but it is not an input that occurs by accident.- Why sorted input matters: it is the most common input a real sort sees — data sorted before, with a few changes. A pivot rule that is worst on sorted input is worst exactly when it matters.
-
Explain how heap sort uses an array as a tree. Describe build-heap and the sort phase, and argue that build-heap is O(n). Why is heap sort often slower in practice than quicksort, though its worst case is better?
Model answer and marking points
- Array as tree:
a[0]is the root; the children ofa[i]area[2i + 1]anda[2i + 2]; the parent isa[(i - 1) // 2]. The tree is complete, height ⌊ log2 n ⌋; there are no pointers. - Build-heap: sift down every parent from
n // 2 - 1down to 0; each sift may assume both subtrees are already heaps. Sort: swap the root (the max) witha[end], shrink the heap toa[0:end], sift the new root down; repeat forend = n - 1 … 1. O(n log n). - Build-heap is O(n): a node at height h sinks at most h levels, and there are at most n/2h+1 such nodes: Σh h n/2h+1 ≤ n. Most nodes are leaves or near them.
- Slower in practice: the sift jumps from
ito2i + 1— far apart in memory, so caches help little — and it makes more comparisons (measured on random data: about 1.7 n log₂ n, against about 1.2 for median-of-three quicksort). Its strength is the guarantee: O(n log n) worst case with O(1) extra space.
- Array as tree:
-
Define a stable sort. Give a practical reason to want one, say which of the six sorts in
dsa/sorting.pyare stable, and explain why sorting(key, tag)tuples does not test stability.Model answer and marking points
- Stable: elements with equal keys come out in the order they went in.
- Why: sorting records by one field after another. Sort students by name, then stably by grade: within a grade they stay in name order.
- In
dsa/sorting.py: bubble, insertion and merge sort are stable; selection, quick and heap sort are not. - Tuples do not test it: Python compares
(key, tag)tuples by the tag when the keys are equal, so every correct sort — stable or not — puts(1, "a")before(1, "c"). A stability test needs values that compare by key only, such as a class whose comparison methods look at the key alone.