Smoothsort: Mechanism, Complexity Analysis & Interactive Visualizer

Smoothsort

A brilliant, adaptive variation of Heapsort developed by Edsger Dijkstra in 1981. It achieves O(n) performance on sorted data while maintaining O(n log n) worst-case performance.

How it works

Standard Heapsort always takes O(n log n) time because converting an already-sorted array to a binary heap scrambles its order. Smoothsort avoids this by using a heap structure based on Leonardo numbers instead of powers of two. The heap is represented as a "forest" of Leonardo trees whose sizes decrease from left to right. When the array is already sorted, it naturally forms a valid Leonardo forest, requiring zero swaps and only O(n) comparisons.

1. The Leonardo numbers are defined as: L(0) = 1, L(1) = 1, and L(k) = L(k-1) + L(k-2) + 1.
2. Build the heap by appending elements one by one. Maintain a bitmask representing the active Leonardo trees in the forest.
3. Use a specialized sift operation to maintain the heap property inside a single tree.
4. Use a specialized trinkle operation to maintain the heap property across the roots of all trees in the forest.
5. During the sorting phase, shrink the forest from right to left, repeatedly placing the root of the largest tree in its sorted position and restoring the forest property.

Complexity

Interactive visualization

JavaScript implementation

function smoothSort(arr) {
  const n = arr.length;
  if (n <= 1) return arr;

  const lp = [1, 1];
  for (let i = 2; ; i++) {
    const next = lp[i - 2] + lp[i - 1] + 1;
    lp.push(next);
    if (next >= n) break;
  }

  function ntz(x) {
    let count = 0;
    while ((x & 1n) === 0n) {
      count++;
      x >>= 1n;
    }
    return count;
  }

  function pntz(x) {
    if (x !== 1n) return ntz(x - 1n);
    return 0;
  }

  function sift(head, pshift) {
    const ar = [head];
    while (pshift > 1) {
      const rt = head - 1;
      const lf = head - 1 - lp[pshift - 2];
      if (arr[ar[0]] >= arr[lf] && arr[ar[0]] >= arr[rt]) break;
      if (arr[lf] >= arr[rt]) {
        ar.push(lf);
        head = lf;
        pshift -= 1;
      } else {
        ar.push(rt);
        head = rt;
        pshift -= 2;
      }
    }
    if (ar.length >= 2) {
      const tmp = arr[ar[0]];
      for (let j = 0; j < ar.length - 1; j++) {
        arr[ar[j]] = arr[ar[j + 1]];
      }
      arr[ar[ar.length - 1]] = tmp;
    }
  }

  function trinkle(head, p, pshift, trusty) {
    const ar = [head];
    while (p !== 1n) {
      const stepson = head - lp[pshift];
      if (arr[stepson] <= arr[ar[0]]) break;
      if (!trusty && pshift > 1) {
        const rt = head - 1;
        const lf = head - 1 - lp[pshift - 2];
        if (arr[rt] >= arr[stepson] || arr[lf] >= arr[stepson]) break;
      }
      ar.push(stepson);
      head = stepson;
      const trail = pntz(p);
      p >>= BigInt(trail);
      pshift += trail;
      trusty = false;
    }
    if (!trusty) {
      if (ar.length >= 2) {
        const tmp = arr[ar[0]];
        for (let j = 0; j < ar.length - 1; j++) {
          arr[ar[j]] = arr[ar[j + 1]];
        }
        arr[ar[ar.length - 1]] = tmp;
      }
      sift(head, pshift);
    }
  }

  let head = 0;
  const high = n - 1;
  let p = 1n;
  let pshift = 1;

  while (head < high) {
    if ((p & 3n) === 3n) {
      sift(head, pshift);
      p >>= 2n;
      pshift += 2;
    } else {
      if (lp[pshift - 1] >= high - head) {
        trinkle(head, p, pshift, false);
      } else {
        sift(head, pshift);
      }
      if (pshift === 1) {
        p <<= 1n;
        pshift = 0;
      } else {
        p <<= BigInt(pshift - 1);
        pshift = 1;
      }
    }
    p |= 1n;
    head++;
  }

  trinkle(head, p, pshift, false);

  while (pshift !== 1 || p !== 1n) {
    if (pshift <= 1) {
      const trail = pntz(p);
      p >>= BigInt(trail);
      pshift += trail;
    } else {
      p <<= 2n;
      pshift -= 2;
      p ^= 7n;
      p >>= 1n;
      trinkle(head - lp[pshift] - 1, p, pshift + 1, true);
      p <<= 1n;
      p |= 1n;
      trinkle(head - 1, p, pshift, true);
    }
    head--;
  }
  return arr;
}

Pros and cons

When to use it

• Partially sorted data: when sorting data that is already mostly ordered, but you need a guaranteed O(n log n) fallback.
• Extremely tight memory limits: in embedded systems or core system utility libraries like libc.