Big Data Sorting: External K-Way Merge Simulator

Dataset Chunks

Sorted runs (k) 4

Records per run 12

Merge speed 4/s

Merge State

Press Play or Step to begin the k-way merge.

Merged

0 / 0

Comparisons

Progress

I/O passes

1 (seq.)

How it works

When a dataset has more records than fit in memory, big-data systems (Hadoop's shuffle sort, database external sorts, LSM-tree compactions) sort it in two phases:

Phase 1 — Sort runs (in memory)
  split N records into k chunks of size N/k
  sort each chunk: O((N/k) log(N/k))
  write each sorted chunk to disk as a "run"

Phase 2 — k-way merge (one sequential pass)
  keep a pointer at the head of each of the k runs
  repeat: scan the k heads, pick the smallest, emit it,
          advance that run's pointer
  cost: O(N log k) comparisons total, O(N) sequential I/O

Sorted runs (k) — how many pre-sorted chunks are merged at once; a real min-heap of size k turns each "scan the heads" step into O(log k) instead of O(k), but the total comparison count scales the same way.
Records per run — the size of each chunk, i.e. how much data fit in memory during Phase 1.
Step — performs exactly one "find the smallest head, emit it" operation, so you can watch the comparisons happen one at a time.
Bar color marks which run a record came from — because the merge only ever compares run heads and never reorders within a run, the output column is a stable, fully sorted interleave of all k runs, produced in a single pass over the data.

This is exactly why systems like Hadoop and Spark write intermediate sorted "spill" files during a shuffle, then merge them — merging is cheap and sequential, while sorting unbounded data in one memory pass usually isn't possible.

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.