 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/imperative-programming/3/f/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 3 / f / Solution by

Codex  0 2026-10-31

Use merge sort, stopping before an empty or singleton linked list would be split.

PROCEDURE MergeSort(less: LESS; VAR p: List);
VAR q, r: List;
BEGIN
  IF p.count > 1 THEN
    Split(p, q, r);
    MergeSort(less, q); MergeSort(less, r);
    Merge(less, q, r, p)
  END
END MergeSort;

By induction on the length, each recursive call returns a sorted permutation of its input. Part (d) makes both child lengths smaller than the parent whenever the parent length exceeds one; part (e) combines the sorted children. No data linked list nodes are newly allocated or lost. Unreachable headers may be reclaimed by garbage collection.

At each level the total splitting and merge algorithm work is linear; approximately equal halves give logarithmic depth. Consequently

Stable ascending sort in O (n lo g (n + 1)) time, with O (lo g (n + 1)) call-stack depth .

(1)

There are

O (n)

header allocations over the whole execution; those allocations should not be confused with the logarithmic call stack bound.

 Read the full article

 New to topics? Read the docs here!