Balanced Multiway Merge Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Balanced Multiway Merge Sort

An advanced external sorting algorithm: distributes runs evenly across a pool of input channels, executing multi-way merges into output channels, dramatically reducing the number of external storage sweep passes.

How it works

Balanced Multiway Merge Sort is a generalization of standard External Merge Sort. Instead of merging just 2 runs at a time (which requires many passes), it uses \(2k\) tape drives or files to execute a \(k\)-way merge, accelerating the process:

1. Initial Run Generation: Read blocks of size \(M\) from RAM. Sort them internally and distribute them evenly across \(k\) input tape drives (e.g. if \(k = 3\), we distribute runs across Tape 1, Tape 2, and Tape 3).
2. K-Way Merge Pass:
   • Read the leading elements of the active runs from all \(k\) input tapes simultaneously.
   • Perform a \(k\)-way comparison merge (often using a Min-Heap or Selection tree in RAM) and write the sorted output run onto one of the remaining \(k\) output tapes (Tape 4, Tape 5, or Tape 6).
   • Cycle through the output tapes for subsequent merged runs to keep the distribution balanced.
3. Role Swapping: Swap the roles of the input and output tapes (Tapes 4, 5, 6 become inputs; Tapes 1, 2, 3 become outputs) and execute another \(k\)-way merge pass. Repeat until only a single sorted run remains.

Complexity

Interactive visualization

Pseudocode

procedure balancedMultiwayMergeSort(inputFile, outputFile, k, M):
  tapes ← initialize2KTapes()
  
  # Phase 1: Generate runs and distribute evenly on first k tapes
  tapeIdx ← 0
  while not EOF(inputFile):
    buffer ← readMRecords(inputFile, M)
    internalSort(buffer)
    writeRun(tapes[tapeIdx], buffer)
    tapeIdx ← (tapeIdx + 1) % k
    
  # Phase 2: Multiway Merging
  inputTapes ← tapes[0 ... k-1]
  outputTapes ← tapes[k ... 2k-1]
  
  while totalRunsCount(inputTapes) > 1:
    outIdx ← 0
    while hasRuns(inputTapes):
      activeRuns ← popOneRunFromEach(inputTapes)
      mergedRun ← kWayMerge(activeRuns)
      writeRun(outputTapes[outIdx], mergedRun)
      outIdx ← (outIdx + 1) % k
      
    swap(inputTapes, outputTapes)
    
  renameFile(getFinalRun(inputTapes), outputFile)

JavaScript implementation

// Simulating 3-way Balanced Multiway Merge Sort on tape partitions
function balancedMultiwayMergeSort(arr, k = 3, M = 3) {
  const n = arr.length;
  
  // 1. Generate runs
  let inputGroup = Array.from({ length: k }, () => []);
  for (let i = 0; i < n; i += M) {
    const run = arr.slice(i, Math.min(i + M, n));
    run.sort((x, y) => x - y);
    // Distribute evenly across k input tapes
    inputGroup[(i / M) % k].push(run);
  }
  
  // 2. Merge runs recursively
  let totalRuns = inputGroup.reduce((sum, t) => sum + t.length, 0);
  while (totalRuns > 1) {
    const outputGroup = Array.from({ length: k }, () => []);
    let outIdx = 0;
    
    while (inputGroup.some(t => t.length > 0)) {
      const activeRuns = [];
      for (let t = 0; t < k; t++) {
        if (inputGroup[t].length > 0) activeRuns.push(inputGroup[t].shift());
      }
      
      // Merge active runs
      const merged = kWayMerge(activeRuns);
      outputGroup[outIdx % k].push(merged);
      outIdx++;
    }
    
    inputGroup = outputGroup;
    totalRuns = inputGroup.reduce((sum, t) => sum + t.length, 0);
  }
  
  // Rebuild array
  const finalRun = inputGroup.find(t => t.length > 0)[0];
  for (let i = 0; i < n; i++) arr[i] = finalRun[i];
  return arr;
}

function kWayMerge(runs) {
  const res = [];
  const ptrs = new Array(runs.length).fill(0);
  while (true) {
    let minIdx = -1;
    let minVal = Infinity;
    for (let p = 0; p < runs.length; p++) {
      if (ptrs[p] < runs[p].length && runs[p][ptrs[p]] < minVal) {
        minVal = runs[p][ptrs[p]];
        minIdx = p;
      }
    }
    if (minIdx === -1) break;
    res.push(minVal);
    ptrs[minIdx]++;
  }
  return res;
}

Pros and cons

When (not) to use it

• High-volume database systems: Standard choice for commercial database managers sorting billions of records.
• Low resources: Avoid when disk space is constrained or tape drive channels are scarce, as Balanced multiway requires double scratch space.