jonnifyfsharp

Dive C4.03.1

Merge sort

Split the list in two, sort each half, then walk the two sorted halves together. The work is in the walk.

Merge sort divides a list positionally — halve it down the middle, no matter what the values are — and spends its effort merging. Two sorted halves combine into one sorted whole by a single pass that always takes the smaller of the two front elements. Because every divide halves the input, there are about log n levels, and each level does O(n) work across all its pieces, so the cost is n log n in every case — there is no pivot to go wrong. And because the merge keeps equal elements in their original order, merge sort is stable. This dive writes it in F# over immutable lists, verified in dotnet fsi, and shows why stability is the property the bus's pending set relies on.

Watch a merge Module hub
C4.03.1 · part 1

Merge two sorted lists into one

The heart of the algorithm is merge: given two lists that are already sorted, produce one sorted list. Compare the two heads; emit the smaller; recurse on the rest. When either list is empty, the other is the answer. In F# the whole function is one match over the pair of lists, and the [], rest | rest, [] pattern handles both empty cases in a single clause.

// merge two already-sorted lists, smaller head first
let rec merge xs ys =
    match xs, ys with
    | [], rest | rest, [] -> rest
    | x :: xt, y :: yt ->
        if x <= y then x :: merge xt (y :: yt)
        else y :: merge (x :: xt) yt

// val merge : xs:'a list -> ys:'a list -> 'a list when 'a : comparison

merge [3; 8] [1; 5]
// val it : int list = [1; 3; 5; 8]
merge
combines two sorted lists into one sorted list in O(m + n): each step emits one element and shrinks the input by one.
x <= y
less-than-or-equal, not strictly less. Taking the left element on a tie is what makes the sort stable.
'a : comparison
the inferred constraint: merge works for any element type the F# compiler knows how to order — int, string, tuples, and more.
C4.03.1 · part 2

Split, recurse, merge

With merge in hand, the sort is short. A list of zero or one element is already sorted, so it is returned unchanged. Otherwise List.splitAt cuts the list at its midpoint into a left and a right half; each half is sorted by a recursive call; and the two sorted halves are merged. The recursion bottoms out at singletons and rebuilds upward.

// merge sort: halve positionally, sort each half, merge
let rec msort lst =
    match lst with
    | [] | [_] -> lst
    | _ ->
        let mid = List.length lst / 2
        let left, right = List.splitAt mid lst
        merge (msort left) (msort right)

// val msort : lst:'a list -> 'a list when 'a : comparison

msort [8; 3; 5; 1]
// val it : int list = [1; 3; 5; 8]

msort [12; 8; 30; 5; 10; 20; 42]
// val it : int list = [5; 8; 10; 12; 20; 30; 42]
In real code you reach for List.sort, which is the F# standard library's stable sort and is exactly this idea, tuned. The hand-written version is here to show the mechanism, not to replace it. List.sort [12; 8; 30; 5; 10; 20; 42] returns the same [5; 8; 10; 12; 20; 30; 42].

Step through a merge

The two halves of [8; 3; 5; 1] sort to [3; 8] and [1; 5]. Step the merge: at each step the smaller of the two front elements moves into the output, and that list advances. The readout names the comparison and what was emitted; the bars show the output filling left to right. This is the exact merge above, run over a fixed dataset.

merge [3; 8] [1; 5] · one comparison per step

left: [3; 8] 3 8 right: [1; 5] 1 5 3 vs 1 output
ready · compare the two heads, 3 and 1 — step to take the smaller into the output.

The whole sort is this merge repeated up a tree of halvings. Every element passes through O(log n) merges, and each merge is one linear pass — that is the n log n, with no pivot to degrade it.

C4.03.1 · part 3

Stability — the tie-break that preserves order

A sort is stable when elements that compare equal keep their original relative order. Merge sort gives this for free: on a tie the merge takes the left element first (the x <= y branch), and the left half always held the earlier elements. F#'s List.sortBy and List.sort are stable for the same reason. The test below sorts pairs by their first component; the second components prove the order of equal keys was preserved.

let pairs = [(2, "a"); (1, "b"); (2, "c"); (1, "d")]

List.sortBy fst pairs
// val it : (int * string) list =
//   [(1, "b"); (1, "d"); (2, "a"); (2, "c")]
// "b" before "d", "a" before "c" — input order kept on every tie

Elixir — Enum.sort is a stable merge sort

# Elixir — the same guarantee
Enum.sort_by([{2, "a"}, {1, "b"}, {2, "c"}, {1, "d"}], &elem(&1, 0))
# => [{1, "b"}, {1, "d"}, {2, "a"}, {2, "c"}]

F# — List.sortBy, the same stable result

List.sortBy fst [(2, "a"); (1, "b"); (2, "c"); (1, "d")]
// [(1, "b"); (1, "d"); (2, "a"); (2, "c")]
Quicksort, the next dive, is not naturally stable: partitioning can reorder equal keys. When order among equals matters — and for the bus it does — merge sort (or a key that breaks every tie) is the choice.
C4.03.1 · the bus

EchoMQ in F#

Status — echo_fs is an in-memory model. The EchoMQ protocol — the Lua transitions executing on a Valkey wire — is not implemented (there is no Lua and no Valkey client in the code); that is the coming-soon transport (EchoMQ.Connector). This block shows how the model uses the structure, not a running bus.

The F# EchoMQ never calls a sort on its hot path, and stability is the reason it does not have to. Its waiting jobs live in a Set<string> of branded ids, and a Set keeps its elements sorted on insert. Because a branded id is time-ordered and fixed-width Base62, that sorted order is arrival order — fixed once, for every later read. The bus gets the merge sort's stable, ordered output as a standing invariant rather than as a step it repeats.

EchoMQ in F#

The sorted set keeps the order; a claim is a pop-minimum

Quoted from echo_fs/EchoMQ/Store.fs: admission adds an id to the pending Set, and a claim takes its Set.minElement — the smallest id, which is the oldest mint. No sort runs; the set was already in order, and removing the minimum leaves it in order. This is the merge sort's guarantee, paid once at insert instead of at every claim.

// echo_fs/EchoMQ/Store.fs — admission adds to the sorted Set
{ st with
    Rows = st.Rows.Add(id, row)
    Pending = st.Pending.Add id }, Admission.Enqueued

// claim the oldest pending job: pop the minimum id (mint order)
let id = Set.minElement st.Pending

The source comment states the property plainly: "Because branded ids are time-ordered and Base62 sorts as the integers do, the id order IS the mint order — the 'no second index' property of the Elixir bus, here for free from Set's ordering."

Status. The in-memory Store serves jobs in mint order today, and EchoMQ.Tests covers it. The Valkey transport (EchoMQ.Connector) keeps the same order in a server-side sorted set when it lands; the wire is the coming-soon part.

Merge sort gives

A stable, ordered sequence at n log n — equal keys keep their input order.

The bus banks it

A Set holds that order as an invariant; the next job is the minimum, found in O(log n), no re-sort.

Where this leads

Merge sort divides positionally and pays its cost in the merge. The next dive is the other divide-and-conquer sort, quicksort, which divides by value around a pivot and pays its cost in the partition — with a different worst case and a different relationship to immutability.

↑ C4.03 · Sorting & searching C4.03.2 · Quicksort → C4.03.3 · Searching

References

Sources

Related in this course