Polyphase Merge Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Polyphase Merge Sort

An optimized external sorting algorithm: distributes sorted runs across tape drives using Fibonacci sequence ratios to continuously merge segments without ever rewinding the tapes.

How it works

During the mainframe era, tape drives were the primary storage medium. Rewinding magnetic tapes was extremely time-consuming. Polyphase Merge Sort, designed by R. L. Gilstad in 1960, solves this by using an asymmetric Fibonacci-based distribution of runs across tape drives, allowing continuous merging with zero rewinding:

1. Fibonacci Distribution: Take \(T\) tape drives. Initial sorted runs are distributed across \(T - 1\) tapes according to Fibonacci numbers of order \(T - 2\). For 3 tapes, the run counts on Tape 1 and Tape 2 follow consecutive standard Fibonacci numbers (e.g. 5 runs on T1 and 3 runs on T2).
2. Asymmetric Merging:
   • Merge runs from T1 and T2 onto the empty T3. Because the capacities are asymmetric (5 vs 3), we merge 3 runs onto T3.
   • T2 becomes empty, T1 has 2 remaining runs, and T3 has 3 merged runs.
   • Next, merge 2 runs from T1 and T3 onto T2. T1 becomes empty, T3 has 1 run, T2 has 2 runs.
   • Merge 1 run from T3 and T2 onto T1. T3 becomes empty, T1 has 1 run, T2 has 1 run.
   • Finally, merge the last 2 runs onto T3, resulting in a single fully sorted run on T3.

Complexity

Interactive visualization

Pseudocode

procedure polyphaseMergeSort(Tapes, P):
  # Phase 1: Distribute runs using Fibonacci numbers
  runCounts ← getFibonacciDistribution(P)
  distributeRunsToTapes(Tapes, runCounts)
  
  # Phase 2: Asymmetric Merge
  while not sorted(Tapes):
    emptyTape ← getEmptyTape(Tapes)
    activeTapes ← getActiveTapes(Tapes)
    
    mergeLimit ← min(getRunCounts(activeTapes))
    
    for i from 1 to mergeLimit:
      mergedRun ← mergeSingleRunFromTapes(activeTapes)
      writeRun(emptyTape, mergedRun)
      decrementRunCounts(activeTapes)

JavaScript implementation

// Demonstrating Polyphase Fibonacci Merge Sort concept on 3 tapes
function polyphaseMergeSort(arr) {
  const n = arr.length;
  // Assume array is partitioned into 8 runs of equal sizes
  let T1 = [arr.slice(0,3), arr.slice(3,6), arr.slice(6,9), arr.slice(9,12), arr.slice(12,15)];
  let T2 = [arr.slice(15,18), arr.slice(18,21), arr.slice(21,24)];
  let T3 = [];
  
  // Sort initial runs internally
  T1.forEach(run => run.sort((x, y) => x - y));
  T2.forEach(run => run.sort((x, y) => x - y));
  
  // Merge T1 & T2 onto T3 (3 runs)
  mergeRuns(T1, T2, T3, 3);
  
  // Merge T1 & T3 onto T2 (2 runs)
  mergeRuns(T1, T3, T2, 2);
  
  // Merge T2 & T3 onto T1 (1 run)
  mergeRuns(T2, T3, T1, 1);
  
  // Merge T1 & T2 onto T3 (1 run - fully sorted)
  mergeRuns(T1, T2, T3, 1);
  
  // Copy result back
  for (let i = 0; i < n; i++) arr[i] = T3[0][i];
  return arr;
}

function mergeRuns(tapeA, tapeB, tapeC, count) {
  for (let k = 0; k < count; k++) {
    const A = tapeA.shift();
    const B = tapeB.shift();
    const res = [];
    let i = 0, j = 0;
    while (i < A.length && j < B.length) {
      if (A[i] <= B[j]) res.push(A[i++]);
      else res.push(B[j++]);
    }
    while (i < A.length) res.push(A[i++]);
    while (j < B.length) res.push(B[j++]);
    tapeC.push(res);
  }
}

Pros and cons

When (not) to use it

• Legacy Systems / Tape Drives: Only useful when sorting datasets using linear tape arrays where head movement must be minimized.
• Modern hardware: Never use in modern databases or SSD-based programs; random-access files don't suffer from rewind latency.