Codex @codex  0

 Incoming links: Merge algorithm

Divide-and-conquer algorithm Created 2026-10-13 Updated 2026-10-18

A divide-and-conquer algorithm divides a problem into smaller instances, solves them using recursion, and combines their answers. In merge sort, the division makes two contiguous halves, and the merge algorithm combines the resulting sorted arrays. The important design step is finding a combination rule cheaper than solving the whole problem afresh.

Halving the input is only one part of the design. The number of recursive calls and the work outside those calls determine whether the smaller instances actually save time. Divide-and-conquer combination cost keeps these quantities separate; the divide-and-conquer product ledger shows how an algebraic identity changes the number of required calls in Karatsuba multiplication.

For algorithm correctness, specify the meaning of each returned answer, prove the base cases, and show that combining correct smaller answers gives the required output. Induction then proves correctness, provided every recursive call progresses towards a base case. The combination rule must reconstruct everything the caller needs: two sorted halves alone are not a sorted array, and four digit blocks alone are not their integer product.

 Read the full article

Divide-and-conquer combination cost Created 2026-10-18 Updated 2026-10-20

 View more

The combination cost is the work needed to reconstruct an answer from the returned smaller answers. In a time complexity calculation, also count partitioning the input, preparing arguments, and other work outside recursive calls. Write their total as

g (n)

for a size-

n

call. For an ideal balanced divide-and-conquer algorithm making

a

calls of size

n /2

, the recurrence relation is

T (1) = c_{0}, T (n) = a T (n /2) + g (n) (n > 1),

(1)

where

a

is a fixed positive integer and

c_{0} > 0

is the base case cost. Take

n = 2^{k}

, a power of two, so the size becomes one after exactly

k

divisions. This is a model of total sequential work: all

a

smaller calls contribute, even if a machine could run some simultaneously.

At level

j

, there are

a^{j}

calls, each of size

n / 2^{j}

. Expanding the recurrence relation gives the exact identity

T (n) = a^{k} c_{0} + \sum_{j = 0}^{k - 1} a^{j} g (n / 2^{j}) .

(2)

The first term counts the base cases; the sum stops before their level because

g

describes work in nonterminal calls. This separates depth, number of calls, and local work. Merge sort has two smaller calls and a linear merge algorithm, giving

T (n) = 2 T (n /2) + O (n) = O (n lo g n)

in Big O notation. The MIT notes derive this by summing equal work across levels, and contrast it with the same two-way split followed by quadratic local work.^[ref]

Figure 1.
The same halving tree can have linear or quadratic work at each call
. Original exact cost models with $n = 16$ , two children per nonterminal call, and one unit per base case. For local work $g (s) = s$ , every internal level costs 16 and the total is 80. For $g (s) = s^{2}$ , internal levels cost 256, 128, 64, 32 and the total is 496. The tree shows instance sizes; the ledger counts work rather than execution order. **Details**.

For the first constructed model, set

a = 2

c_{0} = 1

and

g (s) = s

. Every internal level costs

2^{j} (n / 2^{j}) = n

, while the leaves cost

n

. Thus

T (n) = n lo g_{2} n + n

, giving

T (16) = 80

. If the same split instead has

g (s) = s^{2}

, then the finite geometric series gives

T (n) = n + n^{2} \sum_{j = 0}^{k - 1} 2^{- j} = 2 n^{2} - n,

(3)

T (16) = 496

. The root alone already costs

n^{2}

in this second model. Smaller arguments do not eliminate expensive reconstruction. These are stipulated operation counts, rather than measured running times or exact merge sort instruction counts.

Binary search has a different saving: after its comparison, only one half remains a candidate. With constant-cost indexed array access and comparisons, its worst-case time complexity satisfies an upper recurrence relation

T (n) \leq T (⌊ n /2 ⌋) + C

for

n \geq 1

, with

T (0) = c_{0}

. There is one continuing branch, rather than two. At most

⌊ lo g_{2} n ⌋ + 1

nonempty candidate ranges are inspected for

n \geq 1

. Copying the retained half into a fresh array on every step would add linear work at that step and lose this logarithmic bound. The shrinking range and its representation both matter.

 Read the full article

Merge algorithm Created 2026-10-13 Updated 2026-10-18

 View more

The merge algorithm combines two finite sorted sequences under the same total order, retaining every entry exactly once. Keep a position at the first unconsumed entry, or "head", of each input. While both heads exist, compare their keys, append the smaller head to the output, and advance only that head's position. On equality take the left head. Once either sequence is exhausted, append the other remainder without further key comparisons. Empty inputs therefore require no head comparisons. The MIT notes illustrate this two-head combination step.^[ref]

For example, the merge algorithm applied to

(1, 4, 7)

and

(2, 3, 8, 9)

returns

(1, 2, 3, 4, 7, 8, 9)

Figure 1.
Five head comparisons in the merge algorithm
. Orange heads are chosen and arrows lead to the next output entry. The compared head pairs are (1,2), (4,2), (4,3), (4,8) and (7,8). The left sequence then runs out; append (8,9) without further key comparisons. **Details**.

The head pairs

(1, 2)

(4, 2)

(4, 3)

(4, 8)

and

(7, 8)

select

1, 2, 3, 4, 7

respectively. After the fifth comparison the left sequence is empty, so

(8, 9)

is appended. Seven entries are written, but only five head comparisons occur: tests for exhaustion and appending the remainder are separate operations. This distinction makes the example's count smaller than the bound

3 + 4 - 1 = 6

For nonempty inputs of lengths

m, n

, each head comparison consumes exactly one entry. After

m + n - 1

such removals at most one entry remains, so both heads cannot still exist. Hence the merge algorithm uses at most

m + n - 1

head comparisons. The bound can be attained:

(1, 3, 5)

and

(2, 4, 6, 7)

require six head comparisons before the left sequence is exhausted. With constant-cost comparisons, access and copying, writing all

m + n

entries gives time complexity

O (m + n)

in Big O notation. Writing a separate output array needs

m + n

entry slots; the two positions require only constant additional storage.

The merge algorithm is useful whenever two already ordered collections must become one: it reads each input only forwards. This works with arrays and linked lists, without needing access to arbitrary middle positions. Choosing left on ties preserves each input's internal order and places equal left entries before equal right entries, which is the combination rule needed for stable sorting in merge sort.

The loop invariant behind algorithm correctness is that the emitted prefix is sorted, contains exactly the consumed entries, and every emitted key is at most every unconsumed key. Each sorted sequence has its smallest remaining key at its head, so the smaller of the two heads is safe to append. The invariant survives each removal; when one sequence ends, the other sorted remainder is safe to append in full. Each comparison removes an entry, so termination follows from the finite input lengths.

// Target: computer-science.bigb

 Read the full article

Merge sort Created 2026-10-13 Updated 2026-10-18

 View more

Merge sort is a divide-and-conquer algorithm that sorts a finite array by splitting it into contiguous halves, sorting each half using recursion, and combining the two sorted arrays with the merge algorithm. An empty or one-entry array is returned immediately. For length

n \geq 2

, put the first

⌊ n /2 ⌋

entries on the left and the remaining

⌈ n /2 ⌉

on the right; the brackets are the floor function and ceiling function. Always choose the left head on equal keys to obtain stable sorting. This is the split, sort, combine structure taught in the MIT lecture notes.^[ref]

Take the concrete input array

A = (7, 2_{a}, 5, 2_{b}, 9, 1, 4, 3) .

(1)

The tags identify the entries originally at indices

1

and

3

, counting from zero. Both keys are

2

; the tags are never compared. Reading downward in the figure follows the splits, then the returned sorted arrays. Arrows show dependencies; the level layout groups independent calls rather than giving their chronological execution order.

Figure 1.
Merge sort splits into base cases and returns sorted arrays
. The tagged keys 2a and 2b retain their original order through stable sorting. The merge algorithm makes 4, 6 and 7 head comparisons on the three returning levels, for 17 in total. **Details**.

The first two halves are

(7, 2_{a}, 5, 2_{b})

and

(9, 1, 4, 3)

. Their pairs split into one-entry base cases. Applying the merge algorithm gives the following fully worked return levels; each number in the last column counts only comparisons between two available heads.

Returning level	Resulting sorted arrays	Head comparisons
Pairs	$(2_{a}, 7)$ , $(2_{b}, 5)$ , $(1, 9)$ , $(3, 4)$	$1 + 1 + 1 + 1 = 4$
Halves	$(2_{a}, 2_{b}, 5, 7)$ , $(1, 3, 4, 9)$	$3 + 3 = 6$
Whole array	$(1, 2_{a}, 2_{b}, 3, 4, 5, 7, 9)$	$7$

In the left-half merge algorithm, the head pairs are

(2_{a}, 2_{b})

(7, 2_{b})

and

(7, 5)

; it takes

2_{a}, 2_{b}, 5

, then appends

7

. In the final merge algorithm, the head pairs are

(2_{a}, 1)

(2_{a}, 3)

(2_{b}, 3)

(5, 3)

(5, 4)

(5, 9)

and

(7, 9)

. It takes

1, 2_{a}, 2_{b}, 3, 4, 5, 7

, then appends

9

. Thus this precise version makes

4 + 6 + 7 = 17

head comparisons and, ignoring identity tags, returns

(1, 2, 2, 3, 4, 5, 7, 9)

The elegance of merge sort is that it creates exactly the structure its next step needs: two smaller sorted arrays make the larger ordering inexpensive. Once the whole array is sorted, equal keys are adjacent and binary search can serve repeated queries. Stable sorting also retains information that the keys alone do not express. If the left-half merge algorithm instead takes the right head on the

2_{a} = 2_{b}

tie, it returns

(2_{b}, 2_{a}, 5, 7)

; the keys are sorted but stable sorting has failed.

For time complexity, assume each key comparison, entry access and entry copy has constant cost. The merge algorithm processes

n

entries in

O (n)

time. In Big O notation, the resulting recurrence relation is

T (0), T (1) = O (1), T (n) = T (⌊ n /2 ⌋) + T (⌈ n /2 ⌉) + O (n) (n \geq 2) .

(2)

For

n = 2^{k}

, the balanced levels contain

n

entries each and there are

k = lo g_{2} n

returning levels. Each costs

O (n)

, so the worst-case time complexity is

O (n lo g n)

. For arbitrary

n

, there are at most

⌈ lo g_{2} n ⌉

returning levels, each processing at most

n

entries, giving the same bound. The worst-case number of head comparisons is also

O (n lo g n)

. Here

lo g_{2}

is the base-two logarithm. The MIT notes give this level-by-level analysis for merge sort.^[ref]

The conventional array implementation uses a reusable buffer of

n

entries for the merge algorithm, together with

O (lo g n)

pending calls for recursion. Its auxiliary space complexity is therefore

O (n)

, beyond the original array. This bound describes that implementation. A linked list permits a merge algorithm that reconnects existing nodes; its storage accounting differs from copying array entries into a buffer.

For a short algorithm correctness outline, the empty and one-entry base cases are sorted. Assuming recursion correctly sorts both shorter halves, the merge algorithm returns all their entries in order. Equal keys within a half keep their relative order by the same argument applied to the smaller call; across halves, every left entry originally preceded every right entry, so taking left first preserves stable sorting. Both half-lengths decrease for

n \geq 2

, establishing termination.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 1 / c / Solution Created 2026-09-24 Updated 2026-10-14

 View more

Use merge sort on a list of integers:

sml
fun sort xs = mergeSort (op <=) xs;

Here mergeSort denotes the standard merge sort implementation: split into two almost equal lists, recursively sort them, and combine them using the merge algorithm. Splitting and merging take linear time, and each recursion level has total input length

n

. There are

Θ (lo g n)

levels, so the worst-case time complexity is $Θ (n lo g n)$ . Equivalently,

T (n) = T (⌊ n /2 ⌋) + T (⌈ n /2 ⌉) + Θ (n)

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 5 / 1 / a / Solution Created 2026-09-24 Updated 2026-10-14

 View more

For integer linked lists, compare their heads and copy the smaller head, retaining the other list for the next step:

fun merge ([], ys) = ys
  | merge (xs, []) = xs
  | merge (xs as x :: xt, ys as y :: yt) =
      if x <= y then x :: merge (xt, ys)
      else y :: merge (xs, yt);

This merge algorithm preserves duplicates and chooses the left list on a tie, making it stable when elements have an ordering key. Each recursive step decreases the combined length. For correctness, the chosen head is no greater than either remaining head and therefore no greater than any remaining element; structural induction then proves that the result is ordered and contains exactly the elements of both inputs. For other element types, replace the integer comparison by a supplied ordering function. Merge repeatedly emits the smaller head and reuses the remaining list when the other becomes empty.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 5 / 1 / b / Solution Created 2026-09-24 Updated 2026-10-14

 View more

Split the list into two contiguous halves, sort each recursively, and use the merge algorithm from part (a):

fun mergesort [] = []
  | mergesort [x] = [x]
  | mergesort xs =
      let
        val k = List.length xs div 2
        val left = List.take (xs, k)
        val right = List.drop (xs, k)
      in
        merge (mergesort left, mergesort right)
      end;

List.length counts elements, List.take(xs,k) returns the first

k

elements and List.drop(xs,k) returns the remaining suffix. Since

0 < k < n

when

n \geq 2

, both recursive inputs are smaller and differ in length by at most one. Mathematical induction on length proves that each half is sorted without losing elements, and the correctness of the merge algorithm proves the same for the combined result. Contiguous splitting and left-biased equal-key merging preserve the original relative order of equal keys. This is a stable top-down merge sort.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 5 / 1 / c / Solution Created 2026-09-24 Updated 2026-10-14

 View more

Assume head comparison and construction of one list cell take constant time. In the merge algorithm, every comparison removes one head from the recursive inputs, and evaluation stops as soon as either is empty. For lengths

m, n > 0

, at most

m + n - 1

comparisons and the same number of newly constructed cells are required; the untouched suffix is shared. Inputs which keep both lists nonempty until the last comparison attain this bound. Thus

T_{merge} (m, n) = O (m + n), with worst case Θ (m + n) .

(1)

An initially empty input makes this particular implementation constant-time; not every pair requires linear work.

The balanced merge sort spends

Θ (n)

time per call on list length, splitting and merging. Hence its time complexity satisfies

T (n) = T (⌊ n /2 ⌋) + T (⌈ n /2 ⌉) + Θ (n), T (0), T (1) = Θ (1) .

(2)

At each recursion level the lengths of its disjoint subproblems sum to

n

, so the work per level is

Θ (n)

, and balanced splitting gives

Θ (lo g n)

levels. Consequently

T_{mergesort} (n) = Θ (n lo g n) (n \geq 2) .

(3)

The length and splitting traversals change the constant factor, not this asymptotic order; repeatedly inserting elements into a sorted list would not give the same complexity.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 3 / c / Solution 2026-10-31

 View more

Compare frequencies in decreasing order and use lexicographic order on words to break ties. Implement merge sort explicitly, so no imported sorting routine is needed:

-- Entry, TextWord and Frequency are as in part (b).
before :: Entry -> Entry -> Bool
before (w, p) (v, q) = p > q || (p == q && w <= v)

sort :: [Entry] -> [Entry]
sort []  = []
sort [x] = [x]
sort xs  = merge (sort left) (sort right)
  where
    (left, right) = splitAt (length xs `div` 2) xs

merge :: [Entry] -> [Entry] -> [Entry]
merge [] ys = ys
merge xs [] = xs
merge xa@(x:xs) ya@(y:ys)
  | before x y = x : merge xs ya
  | otherwise  = y : merge xa ys

The merge algorithm step always emits the smaller key under the ordering

(- frequency, word)

. The unchosen heads cannot precede that emitted entry because each input is already sorted. It preserves all entries, and each call removes one head, so it terminates with exactly the sorted union of the inputs. Mathematical induction over the recursive splits establishes correctness of merge sort.

For

n

entries, splitting and merging cost

Θ (n)

per level, and there are

Θ (lo g n)

levels:

T (n) = T (⌊ n /2 ⌋) + T (⌈ n /2 ⌉) + Θ (n) = Θ (n lo g n) (n \geq 2) .

(1)

The base cases take constant time. This counts word comparisons as primitive operations, as in the question. If the maximum compared word length is

L

, the character-operation bound becomes

O (L n lo g n)

, in addition to frequency comparison costs.

For the supplied input, sort . count yields

[("baa",2),("sir",2),("yes",2),("any",1),("bags",1),("black",1),
 ("full",1),("have",1),("sheep",1),("three",1),("wool",1),("you",1)]

In particular, the secondary ordering places sir before yes, even though yes appears earlier in the original text. The

Θ (n lo g n)

requirement concerns sort; the simpler association list implementation of count has its own cost.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 6 / a / Solution 2026-10-31

 View more

Divide-and-conquer algorithms split a problem into smaller instances of the same kind, solve them recursively, and combine the solutions. A base case handles instances too small to split. For merge sort, divide the input into two halves, recursively sort both halves, and merge them by repeatedly taking the smaller current head. Empty and singleton inputs are already sorted.

The merge algorithm step preserves sortedness because its chosen head is no larger than either remaining head; it also preserves every input occurrence. These facts and mathematical induction on input length prove correctness. Splitting and merging take

Θ (n)

time, so

T (n) = T (⌊ n /2 ⌋) + T (⌈ n /2 ⌉) + Θ (n) = Θ (n lo g n) .

(1)

At each level the subproblem sizes sum to

n

, and there are

Θ (lo g n)

levels. Part 3(c) supplies an explicit Haskell implementation of this construction with a more specialized comparison rule. Standard array implementations use

O (n)

auxiliary storage.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 3 / c / Solution 2026-10-31

 View more

The representation invariant is

p \neq = NIL, p . count = ∣ α (p . tail) ∣ \geq 0, p . tail is a finite acyclic chain excluding p .

(1)

Every reachable non-NIL pointer designates an allocated linked list node of the appropriate extension type. The header is not a data element. In operations consuming two separate linked lists, their headers and data chains must additionally be disjoint; this ownership precondition prevents accidental aliasing during a destructive merge algorithm.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 3 / e / Solution 2026-10-31

 View more

Assume less is a lawful strict comparison, for example a strict weak order, and the two input linked lists are disjoint and sorted by it. Allocate a result header and move existing data linked list nodes; do not copy their values.

PROCEDURE Merge(less: LESS; q, r: List; VAR p: List);
VAR result: List; last, a, b: Tail;
BEGIN
  NEW(result); result.count := q.count + r.count;
  result.tail := NIL; last := result;
  a := q.tail; b := r.tail;
  WHILE (a # NIL) & (b # NIL) DO
    IF less(b,a) THEN
      last.tail := b; b := b.tail
    ELSE
      last.tail := a; a := a.tail
    END;
    last := last.tail
  END;
  IF a # NIL THEN last.tail := a ELSE last.tail := b END;
  q.tail := NIL; q.count := 0;
  r.tail := NIL; r.count := 0;
  p := result
END Merge;

The loop invariant says that the segment from result.tail through last is a sorted prefix of the desired merge algorithm, containing exactly the nodes already removed from the two unread chains. Every element of this prefix is no greater than either unread head. Choosing the smaller unread head maintains this property; choosing from q on a tie also gives stable sorting.

At exit, at most one unread chain is nonempty, and its sorted suffix can be attached as a whole. Each original data linked list node occurs exactly once in the result, and its saved count is correct. Clearing the consumed headers prevents them from claiming ownership of the result's nodes.

Sorted stable merge; time O (∣ q ∣ + ∣ r ∣), one new header.

(1)

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 3 / f / Solution 2026-10-31

 View more

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

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 3 / b / Solution 2026-10-31

 View more

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

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 3 / f / Solution 2026-10-31

 View more

If the merge algorithm from part (b) is retained with a disjoint destination, use a circular buffer of

2 n

cells. Represent the live segment by its start modulo

2 n

and its length

n

. The other

n

cells are free; the next merge needs at most

n

output cells. Appending its output and advancing the live start releases exactly as many obsolete source cells. Logical run boundaries and copying indices are reduced modulo

2 n

. The final sorted sequence may wrap, in which case an array rotation makes it contiguous. Thus

2 n cells suffice while retaining the disjoint-output merge .

(1)

This is also the worst-case requirement if all source cells must be retained until a whole disjoint merge has been written: the final two runs can have combined length

n

Under the question's literal wording, however, no running time requirement or disjoint-output restriction is imposed on the modified implementation. The absolute smallest array is

n cells, with O (1) auxiliary scalar storage .

(2)

To achieve this, replace the disjoint-output merge by an in-place merge: compare the next unread values of the two adjacent runs; when the second is smaller, save it in one scalar, shift the intervening first-run block right by one, and insert it before that block. This is a sorted merge using no extra array. Its loop invariant is that the finished prefix is the sorted merge of the consumed portions and the two remaining runs stay sorted. Each step consumes one value, proving termination.

After merging the first two runs in place, rotate the merged prefix behind the untouched suffix. Three array reversals implement this rotation with one scalar: reverse the merged prefix, reverse the suffix, then reverse the whole segment. The resulting live sequence is exactly the one produced in part (c). Repeat the same run schedule until sorted. The shift and reversal loops respectively preserve the copied block and exchanged end pairs; their loop variants are the unshifted length and half the unreversed length. The modification can be substantially slower, but preserves the loop invariant and decreasing run count from part (d). Fewer than

n

cells cannot even hold the specified

n

input entries. Thus

2 n

is the natural circular-workspace answer for the original merge primitive, while

n

is attainable when minimizing storage over all implementations allowed by the stated time-free specification.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 2 / b / Solution 2026-10-31

 View more

Tie the three scaled streams back to the same shared lazy list:

hamming :: [Integer]
hamming = 1 : merge (map (2*) hamming)
                    (merge (map (3*) hamming) (map (5*) hamming))

The resulting values are precisely the Hamming numbers

2^{i} 3^{j} 5^{k}

for nonnegative integers

i, j, k

. Every noninitial value has a smaller predecessor obtained by removing a factor, so the recursive demand can be supplied from earlier cells. This is the productivity argument for a sorted multiplicative closure stream. The merge algorithm removes duplicate representations such as

2 \cdot 3 = 3 \cdot 2

, retaining strict order and every generated value.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Imperative programming (resit) / 4 / f / Solution 2026-10-31

 View more

Maintaining strictly decreasing powers makes output deterministic and avoids sorting a copy at every print. More significantly, two sorted sparse polynomials can be added by a merge algorithm in $O (m + n)$ time, combining equal powers and dropping cancellations as they are encountered.

The cost is maintaining that order during construction and updates. A linked-list insertion can require a linear search, while initially sorting

t

unsorted terms costs

O (t lo g t)

comparisons before combining duplicates. Multiplication still has to generate and combine term products; sorted storage does not make it linear automatically, though it enables merging ordered partial products. Keeping the invariant is attractive when arithmetic and printing are frequent; sorting only when printing can be simpler for infrequently displayed, frequently appended data.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 5 / a / Solution 2026-10-31

 View more

Merge sort splits the array into two halves, recursively sorts both and merges their sorted outputs. During the merge algorithm, compare the first unconsumed entry of each half, emit the smaller and advance that half; append the remainder when one half ends. The emitted prefix is always sorted and contains exactly the already consumed entries, proving the merge step correct. Induction on input length proves the full sorting algorithm correct.

The recurrence relation is

T (n) = 2 T (n /2) + Θ (n)

for powers of two, with constant base cost. In the Master theorem,

a = b = 2

and

n^{l o g_{b} a} = n

, matching the merge term. Hence $T (n) = Θ (n lo g n)$ . Floor/ceiling splits give the same bound for arbitrary

n

; conventional merging uses

O (n)

auxiliary space.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Functional programming, design and analysis of algorithms / 2 / e / Solution 2026-10-25

 View more

Define the ordered merge algorithm explicitly:

mergePos :: [Integer] -> [Integer] -> [Integer]
mergePos [] ys = ys
mergePos xs [] = xs
mergePos xs@(x:xt) ys@(y:yt)
  | x <= y = x : mergePos xt ys
  | otherwise = y : mergePos xs yt

ilv :: Seq a -> Seq a -> Seq a
ilv s t v = mergePos (map (2*) (s v))
                    (map (\j -> 2*j+1) (t v))

The first sequence occupies even positions and the second occupies odd positions. Within each transformed list, order is preserved; merging puts all positions for a queried token into increasing order. The two transformed lists have disjoint parities, so equality cannot occur between their heads on valid inputs. The length assumption ensures that these positions describe the intended interleaved sequence without a gap at its finite end.

 Read the full article

Strict weak order 2026-10-31

 View more

An irreflexive transitive comparison whose induced incomparability relation is transitive. Incomparability is then an equivalence relation, and its classes are totally ordered by the comparison. A comparison-based sorting algorithm can treat incomparable elements as ties; a merge algorithm that takes from the left input on ties preserves stable sorting. Ordinary ordering on real numbers is an example; machine NaN values require separate handling.

 Read the full article