External Merge Sort: Mechanism, Complexity Analysis & Interactive Visualizer

External Merge Sort

The foundational external sorting algorithm: handles datasets too massive to fit in system RAM by generating sorted segments (runs) and merging them back and forth between disk drives.

How it works

External Merge Sort is used when the data size exceeds the main memory capacity (RAM). Instead of loading the entire array into RAM, it uses a two-phase process utilizing scratch storage disks or tape drives:

1. Run Generation:
   • Read blocks of data of size \(M\) (where \(M\) is the maximum RAM capacity) from the unsorted input.
   • Sort each block in memory using a fast internal sort (e.g. Quicksort or Insertion Sort).
   • Write the sorted block out as a temporary file or "run" on a scratch tape.
2. The Merge Phase:
   • Read the first elements of multiple runs concurrently into small RAM buffer streams.
   • Merge the elements (e.g. using a priority queue or tournament tree) and write them to an output file.
   • As buffer streams deplete, pull new values from their respective run files. Repeat until all runs are merged into a single sorted output run.

Complexity

Interactive visualization

Pseudocode

procedure externalMergeSort(inputFile, outputFile, M):
  tempRuns ← empty list
  
  # Phase 1: Generate runs
  while not EOF(inputFile):
    buffer ← readMRecords(inputFile, M)
    internalSort(buffer)
    runFile ← createTempFile()
    writeRecords(runFile, buffer)
    tempRuns.append(runFile)
    
  # Phase 2: Merge runs
  while length(tempRuns) > 1:
    nextRuns ← empty list
    for i from 0 to length(tempRuns) - 1 step 2:
      if i + 1 < length(tempRuns):
        mergedFile ← mergeTwoRuns(tempRuns[i], tempRuns[i+1])
        nextRuns.append(mergedFile)
      else:
        nextRuns.append(tempRuns[i])
    tempRuns ← nextRuns
    
  renameFile(tempRuns[0], outputFile)

JavaScript implementation

// Simulating external merge sort on a mock tape stream
function externalMergeSort(arr, M = 4) {
  const n = arr.length;
  
  // 1. Generate runs of size M
  const runs = [];
  for (let i = 0; i < n; i += M) {
    const run = arr.slice(i, Math.min(i + M, n));
    run.sort((x, y) => x - y);
    runs.push(run);
  }
  
  // 2. Merge runs recursively
  while (runs.length > 1) {
    const mergedRuns = [];
    for (let i = 0; i < runs.length; i += 2) {
      if (i + 1 < runs.length) {
        mergedRuns.push(merge(runs[i], runs[i + 1]));
      } else {
        mergedRuns.push(runs[i]);
      }
    }
    runs.length = 0;
    runs.push(...mergedRuns);
  }
  
  // Rebuild array
  for (let i = 0; i < n; i++) {
    arr[i] = runs[0][i];
  }
  return arr;
}

function merge(A, B) {
  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++]);
  return res;
}

Pros and cons

When (not) to use it

• Large Database engines: Foundational in database management systems (DBMS) such as PostgreSQL or MySQL when sorting large query buffers.
• Standard variables: Never use when values easily fit in local system RAM. Standard in-memory sorts are orders of magnitude faster.