Dive C4.03.2

Quicksort

Pick a pivot, throw everything smaller to the left and everything larger to the right, then do the same to each side.

Where merge sort divides positionally and merges, quicksort divides by value and concatenates. Take the head of the list as a pivot; List.partition splits the rest into the elements smaller than it and the elements at least as large; sort each side recursively; then glue less @ [pivot] @ greater. The work is in the partition, and the combine is a plain concatenation. On a good pivot every split is even and the cost is n log n; on a bad pivot — for instance the first element of an already-sorted list — one side is empty and the cost degrades to n². This dive writes it in F#, verified in dotnet fsi, and reads its cost against merge sort and against immutability.

Partition a list Module hub

C4.03.2 · part 1

Partition around a pivot

The one new piece is the split. List.partition takes a predicate and a list and returns a pair of lists: the elements that satisfy the predicate, and the elements that do not. For quicksort the predicate is "smaller than the pivot". Everything that passes goes left, everything else goes right, and the pivot sits between them once each side is sorted.

// List.partition: one predicate, two lists out
List.partition (fun x -> x < 5) [8; 3; 1]
// val it : int list * int list = ([3; 1], [8])
//   left  = the elements < 5
//   right = the elements >= 5

pivot: the value the rest is compared against. Here the simplest choice — the head of the list — which is also the choice with the worst worst case.
List.partition: splits a list into (pass, fail) in O(n), preserving each side's relative order. The pair is destructured with let less, greater = ….
@: list concatenation. less @ [pivot] @ greater joins the sorted sides around the pivot — the combine step costs O(n) per level.

C4.03.2 · part 2

Recurse on each side, concatenate

The sort is a two-clause match. An empty list is sorted. Otherwise take the head as the pivot, partition the tail, sort each side, and concatenate. There is no separate merge step — once the sides are sorted, joining them around the pivot is the whole answer.

// quicksort: pivot is the head; partition, recurse, concat
let rec qsort lst =
    match lst with
    | [] -> []
    | pivot :: rest ->
        let less, greater = List.partition (fun x -> x < pivot) rest
        qsort less @ [pivot] @ qsort greater

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

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

qsort [12; 8; 30; 5; 10; 20; 42]
// val it : int list = [5; 8; 10; 12; 20; 30; 42]

This functional quicksort is clear but not in-place: each partition builds two new lists, so the memory is not the textbook O(log n) of the array version. The clarity is the point of teaching it; for production work List.sort (a stable merge sort) is the default.

Partition the running sequence

Pick a pivot from [8; 3; 5; 1]. The diagram tints each remaining element by which side of the pivot it falls on, and the readout shows the exact List.partition result and the recursive assembly. A pivot near the middle splits evenly; a pivot at an extreme leaves one side empty — the seed of the n² worst case. Every result shown is the real partition over this fixed list.

qsort [8; 3; 5; 1] · choose the pivot

split balance: even (1 | 1)

A balanced pivot keeps quicksort at n log n; an extreme one starves one side and pushes toward n². Median-of-three or a random pivot makes the bad case rare — but merge sort needs no pivot, and that is why it, not quicksort, is the standard library's sort.

C4.03.2 · part 3

Worst case, comparison cost, and stability

Quicksort and merge sort average the same n log n, but their guarantees differ. Quicksort's cost rides on the pivot: even splits give n log n, the worst pivot gives n². Merge sort always halves, so it is n log n in every case — and stable, where quicksort's partitioning can reorder equal keys.

The comparison itself is where the CLR differs from the BEAM. F# is statically typed, so x < pivot over int compiles to a direct machine comparison with no per-element dispatch; a sort over a custom record uses the type's structural comparison, also resolved at compile time. The BEAM compares terms dynamically at run time. The asymptotics are identical; the constant factor is where the static types pay off.

Elixir — quicksort by value, the E4 sibling

def qsort([]), do: []
def qsort([pivot | rest]) do
  {less, greater} = Enum.split_with(rest, &(&1 < pivot))
  qsort(less) ++ [pivot] ++ qsort(greater)
end

F# — the same shape, statically typed

let rec qsort lst =
    match lst with
    | [] -> []
    | pivot :: rest ->
        let less, greater = List.partition (fun x -> x < pivot) rest
        qsort less @ [pivot] @ qsort greater

Because partitioning is not stable, a sort that must preserve the order of equal keys — such as the bus, whose jobs are ordered by mint time — uses merge sort or a total ordering key. The next dive's Set sidesteps the question by keeping a total order at all times.

C4.03.2 · 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 bus's hot path orders by branded id through a Set, not by calling a sort — but it does reach for List.sort off the hot path, when a payload or a derived field has to be ranked. Quicksort's lesson lands here as a cost lesson: a sort over an F# collection is a comparison sort, so it is bounded below by n log n, and the comparison is whatever the element type defines. A job row's id is a string, so ordering rows by id is a structural string comparison resolved at compile time.

EchoMQ in F#

Ranking job rows by their branded id

The job row is the record below, quoted from echo_fs/EchoMQ/Job.fs. Its Id is a branded-id string; ranking a list of rows by that id is List.sortBy with a structural string comparison — the same comparison the pending Set uses to keep its order. The result is mint order, because the id encodes mint time.

// echo_fs/EchoMQ/Job.fs — the job row
type Job =
    { Id: string
      State: JobState
      Attempts: int
      Payload: string
      // Group, Progress, LastError omitted }

// rank rows by branded id — a comparison sort, O(n log n), stable
rows |> List.sortBy (fun j -> j.Id)
// mint order, because the id encodes the mint time

Status. The in-memory Store keeps order through the Set rather than a per-claim sort, so List.sort is reserved for off-hot-path ranking; EchoMQ.Tests covers the store. The Valkey transport (EchoMQ.Connector) moves the ordering to the server when it lands.

Quicksort teaches

A comparison sort is n log n at best, and the comparison is the element type's own ordering.

The bus applies it

Ranking rows by branded id is a structural string comparison, resolved at compile time — mint order, for free from the id's shape.

Where this leads

Two sorts, one bargain half complete. The next dive is the other half: searching. A sorted sequence answers "where is 20?" by halving — O(log n) — and the same O(log n) is what an F# Set or Map gives, which is how the bus finds a job by id and the due jobs by their run time.

↑ C4.03 · Sorting & searching ← C4.03.1 · Merge sort C4.03.3 · Searching →

References

Sources

FSharp.Core API reference — List.partition, List.sort, and List.sortBy.
Microsoft — F# documentation — lists, recursion, and structural comparison.
The F# Software Foundation — F# on the .NET runtime.
Microsoft — .NET documentation — the framework's sort and comparison interfaces.

Related in this course

Elixir — F4.03.1 · Merge & quicksort — the same two sorts, the E4 sibling.
C4 — Algorithms & Data Structures — the chapter this dive sits in.
C4.03.1 — Merge sort — divide positionally, the stable sort.
C4.03.3 — Searching — what a sorted sequence buys, the next dive.