Merge & quicksort

The two workhorse comparison sorts are both divide-and-conquer — the same split-and-combine recursion you wrote over a tree in F4.02, now applied to a list. Merge sort splits the list in half, sorts each half, and merges the two sorted halves. Quicksort picks a pivot, partitions the rest into smaller and larger, and recurses on each side. Both average O(n log n); they differ in where the work lands.

Merge sort does its work on the way back up, in the merge step; quicksort does it on the way down, in the partition. Select one to see the split over [8, 3, 5, 1].

Divide, then conquer Advanced: worst cases & Enum.sort

Divide, then conquer

Merge sort divides positionally — halve the list regardless of values — and spends its effort merging. Quicksort divides by value around a pivot and spends its effort partitioning. Select an algorithm to see how it breaks the same four elements apart.

The algorithm · select one

step: split, then merge: [3, 8] + [1, 5] → [1, 3, 5, 8]

result: [1, 3, 5, 8]

Both reduce a sort of n things to two sorts of about n/2 things, which is why both average n log n: about log n levels of halving, each doing O(n) work across all its pieces.

Advanced: worst cases & Enum.sort

The averages match, but the worst cases do not. Quicksort’s cost depends on the pivot: if every pivot splits the list evenly it is O(n log n), but a bad pivot — for instance always taking the first element of an already-sorted list — produces one empty side and one of size n−1, degrading to O(n²). Median-of-three or a random pivot makes that practically rare. Merge sort has no pivot and always halves, so it is O(n log n) in every case, and because the merge keeps equal elements in their original order it is stable.

That guarantee is why Elixir’s Enum.sort/1 — and the :lists.sort/1 it builds on — is a stable merge sort, specifically an adaptive one that exploits runs already in order. You rarely write your own; you reach for Enum.sort/2 with a comparator or Enum.sort_by/2 with a key.

# merge sort — always halves, stable, O(n log n) worst case
def msort([]), do: []
def msort([x]), do: [x]
def msort(list) do
  {l, r} = Enum.split(list, div(length(list), 2))
  merge(msort(l), msort(r))
end

defp merge([], r), do: r
defp merge(l, []), do: l
defp merge([h1 | t1] = l, [h2 | t2] = r) do
  if h1 <= h2, do: [h1 | merge(t1, r)], else: [h2 | merge(l, t2)]
end

# quicksort — divides by value; worst case O(n^2) on bad pivots
def qsort([]), do: []
def qsort([pivot | rest]) do
  {less, greater} = Enum.split_with(rest, &(&1 < pivot))
  qsort(less) ++ [pivot] ++ qsort(greater)
end

The idea

Split the problem in two, solve each, and combine — the tree recursion of F4.02, now sorting a list.

In Elixir

Merge splits then merges; quicksort pivots then partitions. Enum.sort is a stable merge sort.

Next: linear & binary search — what a sorted sequence buys you when you go looking for one element.

References

Primary sources for this lesson, and where it connects in the course.

Sources

Merge sort — Wikipedia — a stable functional sort.
Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms (4th ed., 2022) — sorting and searching, in depth.