Distributed Merge Sort

Reported in interviews at Citadel

Problem statement

You are given an array of $N$ integers that is too large to fit on a single machine. The data is partitioned across $K$ machines, with each machine holding roughly $N/K$ elements. Design an algorithm to sort the entire array in a distributed fashion.

Implement the function distributed_sort(machines), where machines is a list of $K$ lists and machines[i] holds the integers on machine $i$ (shards may be unsorted, uneven in size, or empty). Return the single globally sorted list of ALL integers in ascending order (duplicates preserved). Implement the distributed merge-sort idea: sort each shard locally, then merge the sorted runs into the global result.

Constraints:

  • $N$ can be up to $10^{9}$ integers (approximately 4 GB total data)
  • $K$ machines are available, each with enough RAM to sort its local share $N/K$
  • Machines can communicate with each other; minimize inter-machine data transfer
  • You may assume a coordinator node is available if needed

Example

distributed_sort([[5, 3, 8, 1], [7, 2, 6, 4]]) -> [1, 2, 3, 4, 5, 6, 7, 8]

Each machine sorts its shard locally ([1, 3, 5, 8] and [2, 4, 6, 7]); a $K$-way merge then combines the sorted runs into one globally sorted array.

Show hint

Which part of the work can every machine finish on its own before any data crosses the network, and what then dominates the cost?

Relevant roles: ML Engineer, MLOps Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems