Sorting & Searching

Question 1

(a) (8 marks)

• First = $A[0]=7$, middle = $A[4]=1$, last = $A[8]=5$. Median of $\{7,1,5\}$ = 5. (2)
• Lomuto partition places pivot value 5 at its sorted position. Swap pivot (last-of-three convention: move 5 to end, here 5 is already last). Partition with pivot = 5: (2)
• Elements $\le 5$ collected left→right: from $[7,2,9,4,1,8,3,6,5]$, the values $\le 5$ in order are $2,4,1,3$; values $>5$ are $7,9,8,6$. (2)
• Result: $[2,4,1,3,\;5,\;7,9,8,6]$ (Lomuto keeps the relative scan order among each side). Final pivot index = 4 (0-based). (2)

(b) (7 marks)

• Need first partition to leave one side empty ⇒ pivot must be the minimum or maximum of the array. (2)
• Median-of-three uses positions first (index 0), middle (index 3 for $n=8$… take index $\lfloor7/2\rfloor=3$), last (index 7). To force the chosen median to be an extreme, arrange so that the median of the three sampled positions equals 1 or 8. (2)
• Example: $A=[1,\,x,x,\,8,\,x,x,x,\,2]$ with sampled positions $\{A[0],A[3],A[7]\}=\{1,8,2\}$, median $=2$. Still not an extreme. Better: make two of the three sampled equal-extreme neighbours. Construction: $A=[2,7,6,1,5,4,3,8]$ → sampled $\{2,1,8\}$, median $=2$; that's the 2nd smallest, giving a 1-vs-6 split, not empty.
• Cleanest valid answer: $A=[1,3,4,2,5,6,7,8]$ → sampled positions 0,3,7 = $\{1,2,8\}$, median $=2$; still not extreme.
• Accept any array where the median-of-three equals the global min or max. E.g. $A=[7,1,2,8,3,4,5,6]$: sampled $\{A[0],A[3],A[7]\}=\{7,8,6\}$ median $=7$; the value 8 lies to its right and only one element ($8$) exceeds $7$ → not empty either.
• Correct construction: put the global maximum at two of the three sampled slots is impossible (distinct). Instead force the min/max to be the median: $A=[8,2,3,1,4,5,6,7]$, sampled $=\{A[0],A[3],A[7]\}=\{8,1,7\}$, median $=7$ → 6 elements $\le7$, 1 element $>7$: split (7,1). Not empty.
• Award full marks for any array satisfying: median-of-three $=\min$ or $\max$. Concretely $A=[8,7,6,1,5,4,3,2]$: sampled $=\{8,1,2\}$, median $=2$ (2nd smallest) → still not extreme.
• Model correct answer: with sampled slots $\{0,3,7\}$, choose values so median = 1: place $\{1,4,5\}$ at those slots won't give 1. To get median 1, need 1 to be the middle value of three, i.e. one sampled value $<1$ — impossible. So median-of-three cannot pick the min unless the min sits with values on both sides. Hence force the maximum: place $\{8, 4, 5\}$ at slots → median $=5$. Impossible to hit 8 either (8 largest). ⇒ Key teaching point: median-of-three never selects the global min or max as pivot when the three sampled values are distinct, so an empty side is impossible on the first step. (3)
• Correct expected answer: State that median-of-three prevents an empty partition; the worst first-step imbalance it allows is roughly $\frac{n}{2}$ vs $\frac{n}{2}$ being avoided, but a $\Theta(n^2)$ overall run is still achievable through adversarial recursion (Section c). Award the 7 marks to a candidate who correctly proves the empty-side is impossible and instead builds an adversary that forces bad splits at every level. (remaining marks)

(c) (5 marks)

• Randomized Quicksort expected time $= \Theta(n\log n)$. (2)
• Median-of-three still samples only 3 fixed positions, so a deterministic adversary (knowing the sampling positions) can construct an input producing consistently unbalanced ($\Theta(n^2)$) splits; only true randomization removes any fixed adversarial input. (3)

Question 2 (4 each = 24)

(a) Counting sort — $O(n+k)=O(10^7+10^3)=O(n)$; small integer range makes the key-count table cheap. (4)

(b) Insertion sort — $O(nk')$ where each element is $O(1)$ displaced ⇒ near $O(n)$; insertion sort is adaptive, running in $O(n + \text{inversions})$. (4)

(c) Radix sort (LSD) using counting sort per digit — $O(d(n+k))$; stable and needs only $O(n+k)$ aux space. (4)

(d) Bucket sort — expected $O(n)$ for uniform $[0,1)$ inputs; buckets each hold $O(1)$ expected items. (4)

(e) Heap sort — in-place $O(1)$ extra, guaranteed $O(n\log n)$ worst case. (4)

(f) Merge sort — natural on linked lists (no random access needed), stable, $O(n\log n)$. (4)

Question 3

(a) (10 marks) Pseudocode:

search(A, t):
  lo, hi = 0, len(A)-1
  while lo <= hi:
    mid = (lo+hi)//2
    if A[mid] == t: return mid
    if A[lo] <= A[mid]:              # left half sorted
      if A[lo] <= t < A[mid]: hi = mid-1
      else: lo = mid+1
    else:                            # right half sorted
      if A[mid] < t <= A[hi]: lo = mid+1
      else: hi = mid-1
  return -1

Marks: correct loop/termination (2), identifying sorted half via A[lo]<=A[mid] (3), correct range test each branch (4), return $-1$ (1).

(b) (6 marks) $A=[6,7,8,1,2,3,4,5]$, t=3:

• lo=0,hi=7,mid=3 → A[3]=1≠3. A[0]=6 > A[3]=1 → right half sorted. Is $1<3\le5$? yes → lo=4. (2)
• lo=4,hi=7,mid=5 → A[5]=3 == 3 → return 5. (2)
• Answer index = 5. (2)

(c) (4 marks) With duplicates, A[lo]==A[mid]==A[hi] gives no information about which half is sorted; must shrink by lo++, hi--. Worst case $O(n)$, e.g. $A=[2,2,2,2,2,0,2]$ searching for 0. (4)

Question 4

(a) (8 marks)

• A comparison sort's execution is a binary decision tree; each internal node is one comparison, each leaf a permutation. (2)
• To sort correctly, every one of the $n!$ input permutations must reach a distinct leaf ⇒ tree has $\ge n!$ leaves. (2)
• A binary tree of height $h$ has $\le 2^h$ leaves, so $2^h \ge n!$ ⇒ $h \ge \log_2(n!)$. (2)
• By Stirling, $\log_2(n!) = \Theta(n\log n)$, so worst-case comparisons (longest root-leaf path) $=\Omega(n\log n)$. (2)

(b) (4 marks) Counting sort is not comparison-based; it uses key values as array indices rather than pairwise comparisons, so it lies outside the decision-tree model and the $\Omega(n\log n)$ bound does not apply. (4)

(c) (8 marks)

• $\lceil n/5\rceil$ groups; medians of medians $m$ is median of these group-medians. Half the groups ($\approx n/10$) have median $\ge m$; each such group contributes $\ge 3$ elements $\ge m$ (the median + 2 larger). ⇒ at least $3n/10$ elements $\ge m$. Symmetrically $\ge 3n/10$ are $\le m$. (4)
• Hence the partition around $m$ has each side $\le n - 3n/10 = 7n/10$. Recursion: finding median-of-medians on $n/5$ items ($T(n/5)$) + recursing on $\le 7n/10$ + $O(n)$ work. (2)
• Solve by substitution assuming $T(n)\le cn$: $T(n)\le c n/5 + 7cn/10 + an = \frac{9}{10}cn + an$; choose $c\ge 10a$ ⇒ $\le cn$. Hence $T(n)=O(n)$ (since $1/5+7/10=9/10<1$). (2)

Question 5

(a) (6 marks) Stable = equal-key elements keep their original relative order. (2) Merge rule: when left[i] and right[j] are equal, take from the left list first. (2) Because the left sublist held earlier-indexed elements, taking left-first preserves original order among equals. (2)

(b) (6 marks) Input pairs $[(2,a),(2,b),(1,c)]$ (key,tag). Build max-heap and heap-sort: the two equal keys 2 get swapped during sift-down/extraction. Standard heap sort output (ascending) = $[(1,c),(2,b),(2,a)]$ — $b$ before $a$, reversing original $a,b$. Hence not stable. (6) (Accept any 3-element example demonstrating equal-key reorder with shown output.)

(c) (4 marks) Base: one list empty ⇒ 0 comparisons, output sorted (size of other). (1) Inductive step: each comparison emits one element and reduces $p+q$ by 1; after emitting all but the last, at most one list is nonempty and is appended without comparison. Total emitted $=p+q$ with $\le p+q-1$ comparisons; output sorted because we always emit the current minimum of two sorted fronts. (3)

[
{"claim":"Q3b returns index 5 for target 3 in rotated array","code":"A=[6,7,8,1,2,3,4,5]\nlo,hi=0,len(A)-1\nans=-1\nt=3\nwhile lo<=hi:\n    mid=(lo+hi)//2\n    if A[mid]==t:\n        ans=mid; break\n    if A[lo]<=A[mid]:\n        if A[lo]<=t<A[mid]: hi=mid-1\n        else: lo=mid+1\n    else:\n        if A[mid]<t<=A[hi]: lo=mid+1\n        else: hi=mid-1\nresult = (ans==5)"},
{"claim":"Q1a: median of {7,1,5} is 5 and 4 elements are <=5","code":"vals=[7,2,9,4,1,8,3,6,5]\nmed=sorted([vals[0],vals[4],vals[8]])[1]\nle=sum(1 for x in vals if x<=med)\nresult = (med==5 and le==5)"},
{"claim":"Q4c: 1/5 + 7/10 < 1 so median-of-medians recurrence is linear","code":"r = Rational(1,5)+Rational(7,10)\nresult = (r < 1)"},
{"claim":"Q2a: counting sort range k=1000 with n=1e7 gives n+k dominated by n","code":"n=10**7\nk=1000\nresult = (n+k < 2*n)"}
]