Tripos 2025 Paper 1 Question 1 — Worked Solution

Question: Identify five errors in a buggy merge sort implementation and suggest corrections. Then write check_sorted and checksort.

Buggy code:

let length = function
  | [] -> 0
  | _ :: t -> 1 + length t

let rec merge l1 l2 =
  match l1, l2 with
  | [], l -> l
  | h1 :: t1, h2 :: t2 ->
      if h1 <= h2 then h1 :: merge t1 l2
      else h2 :: merge l1 t2

let rec split l l1 l2 n =
  match l, n with
  | [], _ -> (l1, l2)
  | h :: t, 0 -> split t l1 (h :: l2) n
  | h :: t, _ -> split t (l1 :: h) l2 n

let rec mergesort ls =
  match ls with
  | _ ->
      let n = length ls / 2 in
      let l, r = split ls [] [] n in
      merge (mergesort l) (mergesort r)
  | [] | [_] -> ls

(a) Five errors and corrections [10 marks]

Error 1: merge is not exhaustive — missing case ([], _::_). When l1 is [] and l2 is h2 :: t2, the first clause [], l matches and returns l — this is actually correct. But when l1 is h1 :: t1 and l2 is [], neither clause matches. The first clause requires l1 = [], and the second clause requires both l1 and l2 to be non-empty. The pattern h1 :: t1, h2 :: t2 is not matched when l2 = []. Fix: add a clause | l, [] -> l.

Error 2: split — l1 :: h is a type error. The expression split t (l1 :: h) l2 n tries to cons h (an element) onto l1 (a list). But :: expects a list on the right: the element should be h :: l1, not l1 :: h. The parameters to split are (list, front_acc, back_acc, n), so we want h :: l1 to prepend to the front accumulator. Fix: split t (h :: l1) l2 (n-1).

Error 3: split — when n = 0, elements go to l2 but n is not decremented. When n = 0, we prepend h to l2 and recurse with the same n (0). This puts all remaining elements into l2. But we want the first n elements in l1 and the rest in l2. When n = 0, we’ve put all the front elements — we should prepend remaining elements to l2. But the recursive call with n = 0 means split t l1 (h :: l2) 0, which will match h :: t, 0 again — this is actually correct for pushing all remaining elements to l2. However, the n in the non-zero case: Fix: split t (h :: l1) l2 (n-1) — we must decrement n when taking elements for the front list.

Error 4: mergesort — clauses are in wrong order (wildcard _ before [] | [_]). The pattern _ matches everything, so the base cases [] | [_] are unreachable. The mergesort function will always try to split even singleton and empty lists, leading to infinite recursion or division by zero (length of empty list is 0, 0/2 = 0, and split [] [] [] 0 returns ([], []) which recurses forever). Fix: put the base cases first: match ls with | [] | [_] -> ls | _ -> ....

Error 5: split — the n passed to recursive call is wrong when hitting n = 0. When we hit the h :: t, 0 case, we want to put h into l2 and then continue putting all remaining elements into l2. But we pass n (which is 0) unchanged. The recursive call will match h :: t, 0 again — this is fine, it will keep putting elements into l2. Actually, let me reconsider. The intent is: first n elements go to l1 (reversed), the rest go to l2 (reversed). When n = 0, all remaining go to l2. This works with n unchanged at 0. So this isn’t really a bug. But the real issue: when n > 0, we must pass n-1 to the recursive call so we take exactly n elements for the front. The original code passes n unchanged (the wildcard _ matches any n), meaning it never decrements n — it will try to put all elements into l1. Fix: split t (h :: l1) l2 (n-1).

Corrected code:

let rec merge l1 l2 =
  match l1, l2 with
  | [], l -> l
  | l, [] -> l
  | h1 :: t1, h2 :: t2 ->
      if h1 <= h2 then h1 :: merge t1 l2
      else h2 :: merge l1 t2

let rec split l l1 l2 n =
  match l, n with
  | [], _ -> (l1, l2)
  | h :: t, 0 -> split t l1 (h :: l2) 0
  | h :: t, n -> split t (h :: l1) l2 (n - 1)

let rec mergesort ls =
  match ls with
  | [] | [_] -> ls
  | _ ->
      let n = length ls / 2 in
      let l, r = split ls [] [] n in
      merge (mergesort l) (mergesort r)

(b) check_sorted [4 marks]

let rec check_sorted = function
  | [] -> true
  | [_] -> true
  | x :: (y :: _ as rest) ->
      x <= y && check_sorted rest

Time complexity: O(n) where n is the length of the list. We visit each element once, comparing adjacent pairs. In the worst case (the list is sorted), we examine all n-1 adjacent pairs. Space complexity: O(n) stack space because the function is not tail-recursive — the && means the recursive call is nested. This could be made O(1) space with a tail-recursive version:

let check_sorted xs =
  let rec go = function
    | [] | [_] -> true
    | x :: (y :: _ as rest) ->
        if x <= y then go rest else false
  in
  go xs

The tail-recursive version ensures the compiler can optimise stack usage to O(1). It short-circuits on the first out-of-order pair.

(c) checksort [6 marks]

let checksort sorts input =
  let rec check = function
    | [] -> ()
    | sort :: rest ->
        let result = sort input in
        if check_sorted result then check rest
        else
          failwith "Sorting function produced unsorted output"
  in
  check sorts

Explanation: checksort takes a list of sorting functions (all of type 'a list -> 'a list) and an input list. It applies each sorting function to the input and verifies that the result is sorted using check_sorted. If any function produces an unsorted output, it raises Failure with a descriptive message. If all pass, it returns (). The mechanism for signalling unexpected mismatches is OCaml’s built-in failwith which raises a Failure exception.

Better version (with mismatch reporting):

let checksort sorts input =
  let n = List.length sorts in
  let rec check i = function
    | [] -> ()
    | sort :: rest ->
        let result = sort input in
        if not (check_sorted result) then
          failwith (Printf.sprintf "Sort %d produced unsorted output" i)
        else if i > 0 then
          let first_result = (List.hd sorts) input in
          if result <> first_result then
            failwith (Printf.sprintf "Sort %d produced different result from sort 0" i)
          else check (i + 1) rest
        else check (i + 1) rest
  in
  check 0 sorts

Example usage:

(* Assuming quicksort, bubblesort, and insertsort are defined elsewhere *)
let sorts = [mergesort; quicksort; bubblesort; insertsort]
let test_input = [5; 3; 8; 1; 9; 2; 7; 4; 6]
checksort sorts test_input
(* If all sort correctly, returns (). Otherwise raises Failure. *)

Time complexity: For each of k sorting functions applied to an input of length n, the cost is k × T_s(n) where T_s(n) is the sorting time, plus k × O(n) for the check_sorted calls. Space: O(n) for each intermediate sorted list.