Sorting & Searching

Q1. (3 marks)

• Worst case: $O(n^2)$ (reverse-sorted). (1)
• Best case: $O(n)$ (already sorted). (1)
• Average case: $O(n^2)$. Insertion sort wins on nearly-sorted data because each element shifts only a few positions; work is $O(n + I)$ where $I$ = number of inversions, so it is near-linear when $I$ is small. (1)

Q2. (4 marks) Bubble sort passes on $[5,1,4,2,8]$:

• Pass 1: $[1,4,2,5,8]$ (1)
• Pass 2: $[1,2,4,5,8]$ (1)
• Pass 3: $[1,2,4,5,8]$ (no swaps) (1)
• Correct sorted result and stopping recognized. (1)

Q3. (5 marks) Split: $[38,27,43,3,9,82,10] \to [38,27,43,3]\,|\,[9,82,10]$ (1) Down to singletons, then merge:

• $[27,38], [3,43] \to [3,27,38,43]$ (1)
• $[9,82],[10] \to [9,10,82]$ (1)
• Merge $[3,27,38,43]$ and $[9,10,82]$ (1)
• Final: $[3, 9, 10, 27, 38, 43, 82]$ (1)

Q4. (5 marks) Lomuto, pivot $= 4$ (last element), array $[7,2,1,6,8,5,3,4]$. Scan with $i = -1$; increment $i$ and swap when $a[j] \le 4$:

• $j=0$: $7>4$, skip. $j=1$: $2\le4$, $i=0$, swap→$[2,7,1,6,8,5,3,4]$ (1)
• $j=2$: $1\le4$, $i=1$, swap→$[2,1,7,6,8,5,3,4]$ (1)
• $j=3$: $6>4$ skip; $j=4$: $8>4$ skip; $j=5$: $5>4$ skip (1)
• $j=6$: $3\le4$, $i=2$, swap→$[2,1,3,6,8,5,7,4]$ (1)
• Final swap pivot to $i+1=3$: $[2,1,3,4,8,5,7,6]$, pivot index = 3. (1)

Q5. (4 marks)

• Best: $O(n \log n)$ (balanced partitions). (1)
• Average: $O(n \log n)$. (1)
• Worst: $O(n^2)$. (1)
• Worst-case input with last-element pivot: an already-sorted (or reverse-sorted) array, e.g. $[1,2,3,4,5]$. (1)

Q6. (5 marks) Counting sort of $[4,2,2,8,3,3,1]$, indices $0..8$.

• Count array (index→count): $[0,1,2,2,1,0,0,0,1]$ (2) (value 1→1, 2→2, 3→2, 4→1, 8→1)
• Cumulative counts: $[0,1,3,5,6,6,6,6,7]$ (2)
• Output: $[1, 2, 2, 3, 3, 4, 8]$ (1)

Q7. (4 marks)

• Statement: any comparison-based sort requires $\Omega(n \log n)$ comparisons in the worst case. (2)
• Argument: a decision tree sorting $n$ elements must have at least $n!$ leaves (one per permutation). A binary tree of height $h$ has $\le 2^h$ leaves, so $2^h \ge n!$, giving $h \ge \log_2(n!) = \Theta(n\log n)$ by Stirling. (2)

Q8. (5 marks) Array (0-indexed length 10), target 23.

• lo=0, hi=9, mid=4 → $a[4]=16 < 23$, go right. (1)
• lo=5, hi=9, mid=7 → $a[7]=56 > 23$, go left. (1)
• lo=5, hi=6, mid=5 → $a[5]=23$ = target. (2)
• Success at index 5. Mids examined: 4, 7, 5. (1)

Q9. (3 marks)

• (a) Merge sort. (1)
• (b) Heap sort. (1)
• (c) Counting sort (radix or bucket also acceptable). (1)

Q10. (2 marks)

• Complexity: $O(d(n+k))$. (1)
• Linear because with constant $d$ and $k$ it reduces to $O(n)$; it is non-comparison, sorting digit-by-digit with stable counting sort per digit. (1)

[
  {"claim":"Merge sort of [38,27,43,3,9,82,10] gives sorted array",
   "code":"a=[38,27,43,3,9,82,10]; result = sorted(a)==[3,9,10,27,38,43,82]"},
  {"claim":"Counting sort output of [4,2,2,8,3,3,1] is correct",
   "code":"a=[4,2,2,8,3,3,1]; result = sorted(a)==[1,2,2,3,3,4,8]"},
  {"claim":"Lomuto partition with pivot 4 places pivot at index 3",
   "code":"a=[7,2,1,6,8,5,3,4]; piv=a[-1]; i=-1\nfor j in range(len(a)-1):\n    if a[j]<=piv:\n        i+=1; a[i],a[j]=a[j],a[i]\na[i+1],a[-1]=a[-1],a[i+1]\nresult = (i+1==3 and a==[2,1,3,4,8,5,7,6])"},
  {"claim":"Binary search finds 23 at index 5",
   "code":"a=[2,5,8,12,16,23,38,56,72,91]; lo,hi,idx=0,9,-1\nwhile lo<=hi:\n    m=(lo+hi)//2\n    if a[m]==23: idx=m; break\n    elif a[m]<23: lo=m+1\n    else: hi=m-1\nresult = idx==5"}
]