Cascade Merge Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Cascade Merge Sort

A highly sophisticated asymmetric external sort: dynamically decreases the merge fan-in order step-by-step from \(T-1\) down to 2, optimizing tape operations without requiring rewinds.

How it works

Cascade Merge Sort, designed by Margaret K. Butler in 1958, is an alternative to Polyphase Merge Sort. While Polyphase maintains a constant merge order (e.g. always 2-way merges for 3 tapes), Cascade Merge Sort dynamically changes the merge order within each pass. For a system with \(T\) tapes:

1. Asymmetric Distribution: Runs are distributed across \(T - 1\) tapes based on cascade numbers (similar to generalized Fibonacci sequences).
2. Cascading Merge Stage:
   • Start by performing a **\((T - 1)\)-way merge** from the \(T - 1\) active tapes onto the single empty tape until one of the input tapes becomes empty.
   • Immediately switch to a **\((T - 2)\)-way merge** using the remaining non-empty tapes and the newly written tape, merging elements onto the newly empty tape.
   • Continue this cascading process, reducing the merge order at each step, down to a final 2-way merge.
3. Repeat: Once the cascade sweep completes, repeat the cascading stages until a single fully sorted run is produced.

Complexity

Interactive visualization

Pseudocode

procedure cascadeMergeSort(Tapes, T):
  # Phase 1: Distribute runs using Cascade sequence
  distributeRunsCascade(Tapes)
  
  while not sorted(Tapes):
    # Phase 2: Cascading merge steps
    for order from T - 1 down to 2:
      emptyTape ← findEmptyTape(Tapes)
      activeTapes ← selectTapesForMerge(Tapes, order)
      
      while hasRuns(activeTapes):
        mergedRun ← mergeOrderWay(activeTapes, order)
        writeRun(emptyTape, mergedRun)
        decrementRunCounts(activeTapes)

JavaScript implementation

// Simulating Cascade Fibonacci Merge Sort on 4 tapes
function cascadeMergeSort(arr) {
  const n = arr.length;
  // Partition array into 8 runs of size 3
  let T1 = [arr.slice(0,3), arr.slice(3,6), arr.slice(6,9), arr.slice(9,12)];
  let T2 = [arr.slice(12,15), arr.slice(15,18), arr.slice(18,21)];
  let T3 = [arr.slice(21,24)];
  let T4 = [];
  
  T1.forEach(run => run.sort((x, y) => x - y));
  T2.forEach(run => run.sort((x, y) => x - y));
  T3.forEach(run => run.sort((x, y) => x - y));
  
  // 1. 3-way merge from T1, T2, T3 onto T4 (1 run)
  mergeCascade([T1, T2, T3], T4, 1);
  
  // 2. 2-way merge from T1 and T2 onto T3 (2 runs)
  mergeCascade([T1, T2], T3, 2);
  
  // 3. 2-way merge from T3 and T4 onto T2 (1 run)
  mergeCascade([T3, T4], T2, 1);
  
  // 4. 3-way merge from T1, T2, T3 onto T4 (1 run - fully sorted)
  mergeCascade([T1, T2, T3], T4, 1);
  
  for (let i = 0; i < n; i++) arr[i] = T4[0][i];
  return arr;
}

function mergeCascade(tapesList, outputTape, count) {
  for (let step = 0; step < count; step++) {
    const active = tapesList.map(t => t.shift());
    const res = [];
    const ptrs = new Array(active.length).fill(0);
    while (true) {
      let minIdx = -1, minVal = Infinity;
      for (let p = 0; p < active.length; p++) {
        if (ptrs[p] < active[p].length && active[p][ptrs[p]] < minVal) {
          minVal = active[p][ptrs[p]];
          minIdx = p;
        }
      }
      if (minIdx === -1) break;
      res.push(minVal);
      ptrs[minIdx]++;
    }
    outputTape.push(res);
  }
}

Pros and cons

When (not) to use it

• Mainframe magnetic tape units: Historically relevant when sorting multi-gigabyte files on 1960s systems with 6 or 8 tape drives.
• Modern database architectures: Never; modern hardware features quick random-access disk interfaces, negating any benefits.