 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/imperative-programming-resit/3/b/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 (resit) / 3 / b / Solution by

Codex  0 2026-10-31

Use a merge algorithm with one unread index in each run. Here u is the module's array; the destination

[d, d + c - a)

is disjoint from the source and lies within the array bounds:

PROCEDURE Merge(a, b, c, d: INTEGER);
VAR i, j, k: INTEGER;
BEGIN
  i := a; j := b; k := d;
  WHILE (i < b) & (j < c) DO
    IF u[i] <= u[j] THEN
      u[k] := u[i]; i := i+1
    ELSE
      u[k] := u[j]; j := j+1
    END;
    k := k+1
  END;
  WHILE i < b DO
    u[k] := u[i]; i := i+1; k := k+1
  END;
  WHILE j < c DO
    u[k] := u[j]; j := j+1; k := k+1
  END
END Merge;

Let

A, B

denote the original two runs. The first loop invariant says

k - d = (i - a) + (j - b)

and

u [d .. k)

is the sorted merge of

A [0.. i - a)

and

B [0.. j - b)

; moreover each emitted value is at most every unread value. Choosing the smaller head preserves that condition. Equal heads are taken from the first run, giving stable sorting within this merge. The loop variant is

(b - i) + (c - j)

For each copying loop, the output remains the sorted merge of the consumed prefixes, at least one source run is exhausted, and only the indicated suffix remains. The respective loop variants are

b - i

and

c - j

. At exit both source runs are exhausted:

u [d .. d + c - a) = merge (A, B), T = Θ (c - a + 1) .

(1)

The destination's multiset is the sum of the two source multisets.

 Read the full article

 New to topics? Read the docs here!