= Solution
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
$$
\boxed{\text{Stable ascending sort in }O(n\log(n+1))\text{ time, with }O(\log(n+1))\text{ call-stack depth}.}
$$
There are $O(n)$ header allocations over the whole execution; those allocations should not be confused with the logarithmic <call stack> bound.
Back to article page
