Block Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Block Sort

The holy grail of comparison sorts: an in-place, stable hybrid algorithm that achieves O(n log n) efficiency without requiring any auxiliary heap or merge memory buffers.

How it works

For a long time, it was unknown whether a sorting algorithm could be simultaneously stable, **in-place** (\(O(1)\) extra space), and run in **\(O(n \log n)\)** worst-case time. Block Sort (popularized by WikiSort and GrailSort) proves this is possible by restructuring Merge Sort:

1. Block Division: Partition the input array into blocks of size \(\sqrt{n}\).
2. Buffer Extraction: Select a small group of unique elements from the array to act as an internal "buffer". Swap these elements to the beginning of the array.
3. Block Sorting & Tagging: Sort each block individually using Insertion Sort. Use the buffer elements as tags or markers to trace the blocks' relative sorted indices.
4. In-Place Merge: Stably merge adjacent sorted blocks using rotation-based algorithms that move ranges of elements without using external storage arrays.

Complexity

Interactive visualization

Pseudocode

procedure blockSort(A):
  n ← length(A)
  blockSize ← floor(sqrt(n))
  
  for i from 0 to n - 1 step blockSize:
    insertionSort(A, i, min(i + blockSize - 1, n - 1))
    
  for size from blockSize to n step 2 * size:
    for left from 0 to n - 1 step 2 * size:
      mid ← left + size - 1
      right ← min(left + 2 * size - 1, n - 1)
      if mid < right:
        mergeInPlace(A, left, mid + 1, right)

procedure mergeInPlace(A, left, mid, right):
  i ← left
  j ← mid
  while i < j and j ≤ right:
    if A[i] ≤ A[j]:
      i ← i + 1
    else:
      value ← A[j]
      rotateRight(A, i, j)
      A[i] ← value
      i ← i + 1
      j ← j + 1

JavaScript implementation

function blockSort(arr) {
  const n = arr.length;
  if (n <= 1) return arr;
  
  const blockSize = Math.max(2, Math.floor(Math.sqrt(n)));
  
  function insertionSort(left, right) {
    for (let i = left + 1; i <= right; i++) {
      let key = arr[i];
      let j = i - 1;
      while (j >= left && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
      }
      arr[j + 1] = key;
    }
  }
  
  function mergeInPlace(l, m, r) {
    let i = l;
    let j = m;
    while (i < j && j <= r) {
      if (arr[i] <= arr[j]) {
        i++;
      } else {
        const val = arr[j];
        for (let k = j; k > i; k--) {
          arr[k] = arr[k - 1];
        }
        arr[i] = val;
        i++;
        j++;
      }
    }
  }
  
  for (let i = 0; i < n; i += blockSize) {
    insertionSort(i, Math.min(i + blockSize - 1, n - 1));
  }
  
  for (let size = blockSize; size < n; size = 2 * size) {
    for (let left = 0; left < n; left += 2 * size) {
      const mid = left + size - 1;
      const right = Math.min(left + 2 * size - 1, n - 1);
      if (mid < right) {
        mergeInPlace(left, mid + 1, right);
      }
    }
  }
  return arr;
}

Pros and cons

When (not) to use it

• Extremely tight memory budgets: When you need stable sorting but are strictly forbidden from allocating heap memory.
• Standard situations: Standard systems should use Timsort (which has higher space requirements but is faster) or Quicksort (which is in-place but unstable).