Weak Heap Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Weak Heap Sort

A clever sorting algorithm that relaxes the structure of binary heaps to minimize element comparisons, achieving performance extremely close to the information-theoretic lower bound.

How it works

In a standard binary heap, each parent node must be greater than or equal to **both** of its children. Weak Heap Sort relaxes this requirement: each parent node is only required to be greater than or equal to **one** of its children (typically the right child/first child). An auxiliary bit-array of "reverse bits" (denoted as r) tracks whether the left and right children have been swapped. This relaxation makes heap construction incredibly fast (taking exactly n − 1 comparisons) and speeds up extraction significantly.

1. Transform the array into a weak heap bottom-up. Each node is merged with its **distinguished ancestor** (the closest parent reached via a right branch).
2. During a merge, if the child is larger than the ancestor, swap them and toggle the child's reverse bit.
3. To sort, repeatedly swap the root (index 0) with the last element of the heap.
4. Find the leaf along the path of first children starting at index 1.
5. Traverse up from this leaf to the root, merging each node with the root to restore the weak heap property.
6. Swap indices 0 and 1 at the very end to complete the sort.

Complexity

Interactive visualization

Pseudocode

procedure weakHeapSort(A):
  n ← length(A)
  r ← array of size n initialized to 0
  
  for i from n − 1 down to 1:
    j ← i
    while (j & 1) = r[j >> 1]: j ← j >> 1
    parent ← j >> 1
    weakHeapMerge(r, parent, i)
    
  for i from n − 1 down to 2:
    swap A[0], A[i]
    x ← 1
    while (2x + r[x]) < i: x ← 2x + r[x]
    while x > 0:
      weakHeapMerge(r, 0, x)
      x ← x >> 1
  swap A[0], A[1]

procedure weakHeapMerge(r, i, j):
  if A[i] < A[j]:
    swap A[i], A[j]
    r[j] ← r[j] ⊕ 1

JavaScript implementation

function weakHeapSort(arr) {
  const n = arr.length;
  if (n <= 1) return arr;
  
  const r = new Uint8Array(n);
  
  for (let i = n - 1; i > 0; i--) {
    let j = i;
    while ((j & 1) === r[j >> 1]) {
      j = j >> 1;
    }
    const parent = j >> 1;
    merge(arr, r, parent, i);
  }
  
  for (let i = n - 1; i >= 2; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    let x = 1;
    let y;
    while ((y = 2 * x + r[x]) < i) {
      x = y;
    }
    while (x > 0) {
      merge(arr, r, 0, x);
      x = x >> 1;
    }
  }
  [arr[0], arr[1]] = [arr[1], arr[0]];
  return arr;
}

function merge(arr, r, i, j) {
  if (arr[i] < arr[j]) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
    r[j] ^= 1;
  }
}

Pros and cons

When to use it

• Expensive comparisons: sorting large strings or records where comparison key computation dominates execution time.
• Worst-case guarantees needed with minimal comparator overhead: in library structures where standard Heapsort was previously used.