Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 6

Use merge sort: recursively sort the left and right halves of the array, then merge their ordered outputs using two advancing indices. A merge reads or writes each element a constant number of times, so it costs $O(n)$. There are $O(\log n)$ balanced recursion levels with $O(n)$ total work per level. Hence the worst-case running time is $O(n\log n)$; the standard array implementation uses $O(n)$ auxiliary storage.

Yes, if a merge takes from its left half when two sort keys compare equal. Within each half the induction hypothesis preserves equal-key order. Across the two halves every left-half occurrence originally preceded every right-half occurrence, and the tie rule preserves that order. Reversing the tie rule would lose stable sorting.

On $n$ distinct opaque keys, a comparison sorting algorithm must distinguish all $n!$ input orders. Its binary decision tree has at least $n!$ leaves, because one fixed permutation of the input positions cannot correctly sort two distinct strict orders. A tree of height $h$ has at most $2^h$ leaves. Therefore some input needsThe bound is worst-case and specific to algorithms obtaining order information through binary comparisons; it does not apply to every possible representation of keys.

Use counting sort with 26 counters, indexed by the character code minus the code for A. Scan the input to obtain each character's count, then emit that many copies in alphabetic order. Counting costs $O(n)$; visiting 26 counters and writing $n$ outputs costs $O(n+26)=O(n)$.

The comparison lower bound does not apply because the algorithm uses a fixed-size known alphabet and direct key indexing. It does not have to distinguish $n!$ distinct-key orders by binary comparisons; for $n>26$, distinctness is not even possible in this alphabet.

For bare characters, equal occurrences are indistinguishable. The count-and-reconstruct implementation in (d) nevertheless does not preserve the identities of equal-key records, and so cannot provide stable sorting of associated payloads.

A stable refinement computes cumulative counts $C[j]$, the number of input keys at most $j$, then scans the original records right to left. For a record with key $j$, decrement $C[j]$ and place the complete record at output index $C[j]$. Equal-key records are placed from the end of their allocated range in reverse scanning order, preserving their original relative order. This costs $O(n+26)$ time and $O(n+26)$ auxiliary storage.

Precompute the 26 cumulative counts $C[j]=\#\{i:a_i\le j\}$ using prefix sums. Thenand the answer is zero if $c\ge d$. Counting and prefix summation take $O(n+26)=O(n)$ preprocessing time and constant storage for this fixed alphabet. Each query uses two indexed reads and one subtraction, hence $O(1)$ time. The guard for $c>d$ prevents a negative answer for an empty interval.