Codex @codex  0

For heapsort, use the usual array representation of a max-heap, indexed from zero, with children

2 i + 1, 2 i + 2

. Build the max-heap from the last internal node towards the root, using heapify down. The three build stages are

start                    [2,7,3,2,8,1]
sift at index 2          [2,7,3,2,8,1]
sift at index 1          [2,8,3,2,7,1]
sift at index 0          [8,7,3,2,2,1]

At index zero, the value 2 moves below 8 and then below 7. Next exchange the root with the last active element, shorten the active heap, and restore heap order. A vertical separator below distinguishes the active prefix from its sorted final suffix.

Removed maximum	After root exchange	After restoring heap order
$8$	`1,7,3,2,2 \| 8`	`7,2,3,1,2 \| 8`
$7$	`2,2,3,1 \| 7,8`	`3,2,2,1 \| 7,8`
$3$	`1,2,2 \| 3,7,8`	`2,1,2 \| 3,7,8`
$2$	`2,1 \| 2,3,7,8`	`2,1 \| 2,3,7,8`
$2$	`1 \| 2,2,3,7,8`	`1 \| 2,2,3,7,8`

The trace chooses the left child when equal children tie; other tie conventions can give different intermediate heaps with the same sorted output.

For quicksort, use the head as pivot and partition the remaining elements into those strictly less than it and those greater than or equal to it, retaining their order within each partition. This specifies how the duplicate 2 is handled:

pivot 2:  [1]       | 2 | [7,3,2,8]
pivot 7:  [3,2]     | 7 | [8]
pivot 3:  [2]       | 3 | []

Empty and singleton lists are already sorted. Returning from the recursive calls gives

Q [3,2]       = [2] ++ [3] ++ []       = [2,3]
Q [7,3,2,8]   = [2,3] ++ [7] ++ [8]   = [2,3,7,8]
Q [2,7,3,2,8,1] = [1] ++ [2] ++ [2,3,7,8]

For counting sort, count keys

1

through

8

. After reading each input key, the count vector is

initial: (0,0,0,0,0,0,0,0)
read 2:  (0,1,0,0,0,0,0,0)
read 7:  (0,1,0,0,0,0,1,0)
read 3:  (0,1,1,0,0,0,1,0)
read 2:  (0,2,1,0,0,0,1,0)
read 8:  (0,2,1,0,0,0,1,1)
read 1:  (1,2,1,0,0,0,1,1)

The cumulative counts are

(1, 3, 4, 4, 4, 4, 5, 6)

. For the usual stable sorting version with zero-based output indices, scan the input from right to left, place a key

k

at position

C [k] - 1

, and decrement

C [k]

. The successive placements are 1 at

0

, 8 at

5

, the later 2 at

2

, 3 at

3

, 7 at

4

, and the earlier 2 at

1

. The final answer for all three sorting algorithms is

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

Heapsort uses

Θ (n)

time for bottom-up heap construction and

O (lo g n)

for each extraction, giving

Θ (n lo g n)

worst-case time complexity. An iterative heapify down on an array uses

O (1)

auxiliary space complexity. Ordinary heapsort is not a stable sorting method.

Quicksort has balanced-case and average-case

Θ (n lo g n)

time complexity when the input order supplies suitably distributed pivot ranks. With the prescribed first-element pivot, sorted inputs produce subproblems of sizes

0

and

n - 1

, giving

T (n) = T (n - 1) + Θ (n) = Θ (n^{2})

. With the stated two-way partition convention, all-equal keys also give this worst case. There is no input-independent expected bound without a distribution or randomization assumption. For an in-place array implementation, the recursion stack is

O (lo g n)

when balanced and

O (n)

in the worst case; the functional list trace also allocates new partition spines and copied concatenation prefixes. Ordinary in-place quicksort is not stable sorting; the stable-partition list convention used in the trace can preserve equal-key order at additional allocation cost.

Counting sort uses

Θ (n + k)

time complexity for

k

possible consecutive integer keys. The stable sorting version uses

Θ (n + k)

auxiliary space complexity including the output array; counting and re-emitting bare keys needs only

O (k)

beyond its output. It is attractive when

k

is small, but a sparse huge key range makes both initialization and count storage expensive. It relies on indexing by bounded integer keys, so it is not subject to the comparison sorting lower bound.

heapsort: Θ (n lo g n); quicksort worst case: Θ (n^{2}); counting sort: Θ (n + k) .

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 6 / c / i / Solution 2026-10-31

Assume

1 \leq i \leq n

. Apply a worst-case

Θ (n lo g n)

comparison sort, such as merge sort or heapsort, to the whole array, then copy its first

i

entries to the output. The copying costs

Θ (i)

, so

T_{1} (n, i) = Θ (n lo g n + i) = Θ (n lo g n) (n \geq 2) .

The comparison sorting lower bound makes the full-sort stage tight. For the sample array, the sorted order begins

2, 6, 7

, which is the required prefix for

i = 3

. This method spends time ordering all

n - i

unreported elements as well.

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 4 / a / Solution 2026-10-31

Maintain an integer len, initially zero, with len = length xs:

PROCEDURE Add(x: INTEGER);
BEGIN
  ASSERT(len < N);
  u[len] := x;
  len := len+1
END Add;

The precondition is the abstract capacity condition. Appending at the first unused array index establishes

u [0.. len) = x s^{'}

in constant running time.

If get(k) first applies a comparison sort to all

n = len

entries, the comparison sorting lower bound gives at least

⌈ lo g_{2} (n!)⌉ = Ω (n lo g n)

comparisons in the worst case. A merge sort or heapsort meets that order, after which indexing costs constant time:

add : Θ (1), get by comparison sorting : Θ (n lo g n) optimally in the worst case .

This is a logarithmic factor worse than linear. The qualification to comparison sorting is necessary: merely saying that keys are integers does not prohibit counting sort for a bounded small range or radix sort under suitable machine-key assumptions. The printed assertion of an unavoidable superlinear bound needs the comparison model.

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms (resit) / 8 / a / Solution 2026-10-31

Build a max-heap, then repeatedly swap its root with the last element of the active prefix, shrink that prefix and restore heap order by heapify down. A zero-based implementation is

for i = floor(n/2)-1,...,0:
    siftDown(A,i,n)
for end = n-1,...,1:
    swap A[0],A[end]
    siftDown(A,0,end)

siftDown(A,i,end) repeatedly exchanges entry i with its larger child while the child lies below end and has a larger key. The suffix beyond end is already sorted and never touched again. For the specified input, key stages of heapsort are

Stage	Active max heap	Sorted suffix
Bottom-up heap construction	$[5, 4, 3, 1, 2]$	$[]$
Extract 5, repair	$[4, 2, 3, 1]$	$[5]$
Extract 4, repair	$[3, 2, 1]$	$[4, 5]$
Extract 3, repair	$[2, 1]$	$[3, 4, 5]$
Extract 2	$[1]$	$[2, 3, 4, 5]$

The final array is $[1, 2, 3, 4, 5]$ . Bottom-up construction takes

O (n)

time because there are progressively fewer nodes at each greater subtree height; the extractions give worst-case

O (n lo g n)

time and constant auxiliary storage for iterative sifting.

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms (resit) / 8 / d / Solution 2026-10-31

Prefer the alternatives for large unrestricted arrays. Merge sort and heapsort have

O (n lo g n)

worst-case time, while insertion sort has

O (n^{2})

worst-case time and can be much faster on nearly sorted data. The intended stooge sort has worst-case

Θ (n^{2.7095 \dots})

, so even insertion sort has the better worst-case exponent.

The first two give the stronger general asymptotic guarantee. Choices between them can depend on storage and stable sorting requirements; these considerations do not rescue Stooge sort's much larger work count.