Replacement Selection Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Replacement Selection Sort

An optimized run generation algorithm: uses a Min-Heap buffer to stream sorted runs to disk, producing runs that are on average twice the size of available system RAM.

How it works

Replacement Selection Sort is an algorithm used during the **Run Generation Phase** of external sorting. Instead of reading \(M\) items into RAM, sorting them, and writing a run of size \(M\) (like standard External Merge Sort), it uses a Min-Heap structure to stream longer runs:

1. Heap Initialization: Fill a Min-Heap of size \(M\) with the first \(M\) elements from the input stream.
2. Stream Loop:
   • Pop the minimum element (\(min\)) from the heap and write it to the current output run.
   • Read the next element (\(x\)) from the input stream.
   • If \(x \ge min\), insert \(x\) into the active Min-Heap. It can join the current ascending run.
   • If \(x < min\), it cannot join the current run. Mark \(x\) as **dead** for this run, placing it in a secondary inactive buffer inside the heap.
3. New Run Boundary: When all elements in the heap become marked as dead, the current run ends. Revive all dead elements to form a new active Min-Heap, write a run-separator, and start the next run.
4. Result: On average, if the input is random, this heap replacement technique yields runs of size **\(2M\)**, halving the number of run files needed for the subsequent merge phases.

Complexity

Interactive visualization

Pseudocode

procedure replacementSelectionSort(inputStream, outputStream, M):
  heap ← array of size M
  fillHeapFromStream(heap, inputStream)
  activeSize ← M
  
  while activeSize > 0:
    minRecord ← popMin(heap, activeSize)
    writeRecord(outputStream, minRecord)
    
    nextRecord ← readNextRecord(inputStream)
    if nextRecord == EOF:
      activeSize ← activeSize - 1
    else if nextRecord >= minRecord:
      insertIntoHeap(heap, nextRecord, activeSize)
    else:
      # Dead element: push to back of heap array
      deadIndex ← activeSize - 1
      heap[deadIndex] ← nextRecord
      activeSize ← activeSize - 1
      
    if activeSize == 0 and length(heap) > 0:
      # Start a new run
      writeRunSeparator(outputStream)
      activeSize ← length(heap)
      rebuildHeap(heap, activeSize)

JavaScript implementation

function replacementSelectionSort(arr, M = 4) {
  const n = arr.length;
  const output = [];
  
  let inputPtr = 0;
  let heap = [];
  
  while (heap.length < M && inputPtr < n) {
    heap.push({ val: arr[inputPtr++], dead: false });
  }
  
  while (heap.length > 0) {
    // Find minimum of active elements
    let minIdx = -1;
    let minVal = Infinity;
    for (let i = 0; i < heap.length; i++) {
      if (!heap[i].dead && heap[i].val < minVal) {
        minVal = heap[i].val;
        minIdx = i;
      }
    }
    
    if (minIdx === -1) {
      // Start new run, revive dead records
      heap.forEach(item => item.dead = false);
      continue;
    }
    
    output.push(minVal);
    
    if (inputPtr < n) {
      const nextVal = arr[inputPtr++];
      heap[minIdx] = { val: nextVal, dead: nextVal < minVal };
    } else {
      heap.splice(minIdx, 1);
    }
  }
  
  for (let i = 0; i < n; i++) arr[i] = output[i];
  return arr;
}

Pros and cons

When (not) to use it

• Run Generation Pipelines: The standard first phase in DBMS external sorting algorithms to reduce the subsequent merge fan-in passes.
• Already sorted streams: Extremely fast if data has natural ascending trends.