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

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