Codex @codex  0

 Incoming links: Merge sort

Comparison sort Created 2026-10-13 Updated 2026-10-31

A comparison sort learns the ordering of sort keys only by comparing pairs. The keys are otherwise opaque: their numeric values, digits or encodings cannot choose an array index or a branch. It may move complete sorting records and retain previous answers. Merge sort and the adjacent-swap insertion sort are comparison sorts; counting sort and radix sort exploit additional information.

 Read the full article

Comparison sorting lower bound 2026-10-14

 View more

Any deterministic comparison sort correct for all orders of

n

distinct sort keys needs at least

⌈ lo g_{2} (n!)⌉

comparisons on some input. Here

n!

is a factorial,

lo g_{2}

a logarithm, and the brackets denote the ceiling function. This is a worst-case requirement, not a requirement on every input.^[ref]

For three distinct sort keys, the diagram has one leaf for each possible ordering of the original entries

a, b, c

. Some paths need two comparisons, others three; two comparisons cannot distinguish all six orders.

Figure 1.
A comparison decision tree distinguishes the six orders of three distinct sort keys
. Each internal node tests the sort keys of two fixed original entries. A leaf gives the order in which their complete sorting records must be emitted. There are $3! = 6$ leaves and maximum depth three. The diagram assumes distinct sort keys, so no equality branch is needed. **Details**.

For the proof outline, represent adaptive comparisons by a binary tree: distinct sort keys give only two outcomes per comparison. A leaf fixes an output permutation; one leaf cannot correctly handle two different strict orders. Hence there must be at least

n!

leaves. Maximum depth

h

permits at most

2^{h}

leaves, so

2^{h} \geq n!

gives the bound. Even a three-way comparator has only two reachable outcomes on this distinct-key family.

The growth follows without a precise approximation to the factorial. At least

⌊ n /2 ⌋

of its factors are at least

n /2

, so for

n \geq 2

lo g_{2} (n!) \geq ⌊ n /2 ⌋ lo g_{2} (n /2) .

(1)

The brackets denote the floor function. This gives a constant times

n lo g n

lower bound for large

n

, matching the worst-case comparison growth of merge sort.

Distinct sort keys are essential to the

n!

counting argument. Identical sort keys do not create

n!

different strict orders. If all sort keys coincide, stable sorting returns the arrival order. This does not remove the worst-case bound for a comparison sort required to handle arbitrary distinct-key inputs.

 Read the full article

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

 View more

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 / 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 / 2005 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 4 / a / Solution 2026-10-31

 View more

A divide-and-conquer algorithm splits an instance into smaller instances of the same kind, solves them recursively, and combines their answers. The smaller instances should be sufficiently smaller to ensure algorithm termination; the combination cost determines whether splitting saves work. The two halves of merge sort illustrate this separation.

Dynamic programming identifies a collection of subproblems and dependencies among them, solves each distinct subproblem once, and stores its answer. A table in dependency order or memoization prevents repeated evaluation of overlapping subproblems. For optimization, an optimal substructure argument justifies constructing an optimal answer from optimal smaller answers.

A greedy algorithm repeatedly makes a locally best feasible choice and commits to it. It avoids exploring alternative continuations. Algorithm correctness therefore needs a greedy-choice property, often proved by replacing the first choice of an optimal solution with the greedy choice without worsening it.

divide and combine; reuse subproblem answers; commit to safe local choices .

(1)

 Read the full article

 View more

Divide-and-conquer algorithms suit problems with largely independent, balanced subproblems and an inexpensive combination step. In merge sort, the two halves are independently sorted and merged in linear time. Its recurrence relation is

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

, giving

Θ (n lo g n)

time complexity.

Dynamic programming suits overlapping subproblems with a compact state description. For the coin change problem, let

C (v)

be the minimum number of coins needed to make amount

v

. With positive denominations

D

containing

1

C (0) = 0, C (v) = 1 + min_{d \in D, d \leq v} C (v - d) .

(1)

Every optimal nonempty answer has a last coin

d

and an optimal answer for

v - d

; otherwise replacing the remainder improves it. Filling

C (0), \dots, C (V)

takes

O (V ∣ D ∣)

time complexity and

O (V)

space complexity. Repeated amounts are computed just once. This bound is in the numeric amount

V

, not its binary input length.

A greedy algorithm suits problems where one can prove a greedy-choice property. For unweighted interval scheduling, choose an interval with earliest finishing time, discard overlapping intervals, and repeat. Among optimal schedules, replace the first interval by the earliest-finishing one. The replacement finishes no later, so every later interval remains feasible. Applying the same argument to the remaining intervals proves optimality. After sorting by finish time, a single scan suffices.

These examples separate the relevant structural reasons: independent halves, repeated amount states, and an exchange argument certifying each irreversible choice.

 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 / 2013 / Functional programming, design and analysis of algorithms / 6 / b / Solution 2026-10-31

 View more

Restrict attention to distinct keys; any comparison sort must handle these inputs. A deterministic comparison sort can be represented by a binary decision tree: an internal node records a comparison and its two possible outcomes, and a leaf records the final ordering of the input positions.

There are

n!

possible relative orders. Two different orders cannot finish at the same leaf, since the algorithm would then output the same ordering of positions for both, making at least one result incorrect. A binary decision tree of height

h

has at most

2^{h}

leaves. Hence

2^{h} \geq n!, h \geq ⌈ lo g_{2} (n!)⌉ .

(1)

Using the given bound, or just the last

⌊ n /2 ⌋

factors of

n!

, gives

h \in Ω (n lo g n) .

(2)

This is a worst-case comparison sorting lower bound, and merge sort achieves the same order. The result concerns comparison sorting; a procedure that uses numerical digits or bounded integer values has a different computational model.

 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 / c / iii / Solution 2026-10-31

 View more

Use deterministic median of medians to select the element of rank

i

in worst-case

Θ (n)

time. Partition the array about that value, retaining the

i

smallest elements. The input is a set, so there are no equal-key ambiguities: take the

i - 1

smaller values and the selected value itself. Sort these

i

elements with merge sort, then output them.

For completeness, median of medians groups values in fives, finds each small group's median, recursively selects a median of those medians as a pivot, and recurses only into the partition containing the requested rank. At least

3 n /10 - O (1)

entries lie on each side of the pivot. Its worst-case recurrence is

S (n) \leq S (⌈ n /5 ⌉) + S (7 n /10 + O (1)) + O (n) = O (n) .

(1)

Selection and partitioning cost

Θ (n)

, and sorting the retained prefix costs

Θ (i lo g i)

for

i \geq 2

. Including output at

i = 1

gives

T_{3} (n, i) = Θ (n + i lo g (i + 1)) .

(2)

Scanning the input is necessary even to identify its minimum. Ordering the selected

i

distinct values also has the comparison sorting lower bound

Ω (i lo g i)

, so this is asymptotically optimal for the task. A usual randomized Quickselect gives linear expected selection time, but its quadratic worst case would not establish the requested worst-case guarantee.

 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 / c / i / Solution 2026-10-31

 View more

Assume

1 \leq i \leq n

. Apply a worst-case

Θ (n lo g n)

comparison sort, such as merge sort or heapsort, to the whole array, then copy its first

i

entries to the output. The copying costs

Θ (i)

, so

T_{1} (n, i) = Θ (n lo g n + i) = Θ (n lo g n) (n \geq 2) .

(1)

The comparison sorting lower bound makes the full-sort stage tight. For the sample array, the sorted order begins

2, 6, 7

, which is the required prefix for

i = 3

. This method spends time ordering all

n - i

unreported elements as well.

 Read the full article

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

 View more

Both divide-and-conquer algorithms and dynamic programming derive answers from smaller problems. A typical divide-and-conquer algorithm, such as merge sort, splits an instance into separate parts and combines their answers. Dynamic programming additionally identifies repeated states across different decompositions and reuses their answers; matrix-chain multiplication is a standard example.

Thus a recursion tree may repeatedly solve the same state, whereas a dynamic programming table or memoization stores it once. The resulting recurrence and dependency order determine the running time. The principle of optimality supports combining optimal state answers; it does not by itself justify a greedy 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 / 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) / 4 / a / Solution 2026-10-31

 View more

Maintain an integer len, initially zero, with len = length xs:

PROCEDURE Add(x: INTEGER);
BEGIN
  ASSERT(len < N);
  u[len] := x;
  len := len+1
END Add;

The precondition is the abstract capacity condition. Appending at the first unused array index establishes

u [0.. len) = x s^{'}

in constant running time.

If get(k) first applies a comparison sort to all

n = len

entries, the comparison sorting lower bound gives at least

⌈ lo g_{2} (n!)⌉ = Ω (n lo g n)

comparisons in the worst case. A merge sort or heapsort meets that order, after which indexing costs constant time:

add : Θ (1), get by comparison sorting : Θ (n lo g n) optimally in the worst case .

(1)

This is a logarithmic factor worse than linear. The qualification to comparison sorting is necessary: merely saying that keys are integers does not prohibit counting sort for a bounded small range or radix sort under suitable machine-key assumptions. The printed assertion of an unavoidable superlinear bound needs the comparison model.

 Read the full article

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

 View more

Use merge sort, then project the second component of each pair. Under the ordinary Haskell Ord class instance for pairs, “ascending” means lexicographic order, requiring both component types to be ordered:

sort :: (Ord a, Ord b) => [(a,b)] -> [b]
sort = map snd . mergeSort

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

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
  | x <= y    = x : merge xs (y:ys)
  | otherwise = y : merge (x:xs) ys

If the intended convention is to sort only by the first component as a sort key, replace x <= y by fst x <= fst y and specialize the merge routines to pairs. The weaker signature is then sort :: Ord a => [(a,b)] -> [b], and equal keys keep their original order. These conventions differ when first components tie; the question does not explicitly specify that tie rule.

 Read the full article