Ternary Heap Sort — VisualAlgorithms Docs

How it works

Heap sort built on a ternary (3-ary) heap: every node has up to three children, so the heap is shallower than a binary heap and each sift-down visits fewer levels. Builds a max-heap in place, then repeatedly swaps the root to the end and restores the heap over the shrinking prefix.
Implementation

      
 function ternaryHeapSort(arr, stats) {
  const n = arr.length;
  function siftDown(size, root) {
    while (true) {
      let largest = root;
      const c1 = 3 * root + 1;
      const c2 = 3 * root + 2;
      const c3 = 3 * root + 3;
      if (c1 < size) {
        compare(c1, largest);
        if (arr[c1] > arr[largest]) largest = c1;
      }
      if (c2 < size) {
        compare(c2, largest);
        if (arr[c2] > arr[largest]) largest = c2;
      }
      if (c3 < size) {
        compare(c3, largest);
        if (arr[c3] > arr[largest]) largest = c3;
      }
      if (largest === root) break;
      [arr[root], arr[largest]] = [arr[largest], arr[root]];
      swap(root, largest);
      root = largest;
    }
  }
  for (let i = Math.floor((n - 2) / 3); i >= 0; i--) {
    siftDown(n, i);
  }
  for (let end = n - 1; end > 0; end--) {
    [arr[0], arr[end]] = [arr[end], arr[0]];
    markSorted(end);
    swap(0, end);
    siftDown(end, 0);
    checkpoint(n - end, n);
  }
  markSorted(0);
}
 def ternaryHeapSort(arr, stats):
    def siftDown(size, root):
        while True:
            largest = root
            c1 = ((3 * root) + 1)
            c2 = ((3 * root) + 2)
            c3 = ((3 * root) + 3)
            if (c1 < size):
                compare(c1, largest)
                if (arr[c1] > arr[largest]):
                    largest = c1
            if (c2 < size):
                compare(c2, largest)
                if (arr[c2] > arr[largest]):
                    largest = c2
            if (c3 < size):
                compare(c3, largest)
                if (arr[c3] > arr[largest]):
                    largest = c3
            if (largest == root):
                break
            arr[root], arr[largest] = arr[largest], arr[root]
            swap(root, largest)
            root = largest

    for i in range(((n - 2) // 3), (0 - 1), -1):
        siftDown(n, i)
    for end in range((n - 1), 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        markSorted(end)
        swap(0, end)
        siftDown(end, 0)
        checkpoint((n - end), n)
    markSorted(0)
 #include <vector>
#include <algorithm>
void siftDown(int size, int root);

void siftDown(int size, int root) {
    while(1) {
        int largest = root;
        int c1 = ((3 * root) + 1);
        int c2 = ((3 * root) + 2);
        int c3 = ((3 * root) + 3);
        if((c1 < size)) {
            compare(c1, largest);
            if((arr[c1] > arr[largest])) {
                largest = c1;
            }
        }
        if((c2 < size)) {
            compare(c2, largest);
            if((arr[c2] > arr[largest])) {
                largest = c2;
            }
        }
        if((c3 < size)) {
            compare(c3, largest);
            if((arr[c3] > arr[largest])) {
                largest = c3;
            }
        }
        if((largest == root)) {
            break;
        }
        std::swap(arr[root], arr[largest]);
        swap(root, largest);
        root = largest;
    }
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    for(int i=((n - 2) / 3); i>(0 - 1); i--) {
        siftDown(n, i);
    }
    for(int end=(n - 1); end>0; end--) {
        std::swap(arr[0], arr[end]);
        markSorted(end);
        swap(0, end);
        siftDown(end, 0);
        checkpoint((n - end), n);
    }
    markSorted(0);
} void siftDown(int size, int root) {
    while(true) {
        int largest = root;
        int c1 = ((3 * root) + 1);
        int c2 = ((3 * root) + 2);
        int c3 = ((3 * root) + 3);
        if((c1 < size)) {
            compare(c1, largest);
            if((arr[c1] > arr[largest])) {
                largest = c1;
            }
        }
        if((c2 < size)) {
            compare(c2, largest);
            if((arr[c2] > arr[largest])) {
                largest = c2;
            }
        }
        if((c3 < size)) {
            compare(c3, largest);
            if((arr[c3] > arr[largest])) {
                largest = c3;
            }
        }
        if((largest == root)) {
            break;
        }
        { int _t = arr[root]; arr[root] = arr[largest]; arr[largest] = _t; }
        swap(root, largest);
        root = largest;
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    for(int i=((n - 2) / 3); i>(0 - 1); i--) {
        siftDown(n, i);
    }
    for(int end=(n - 1); end>0; end--) {
        { int _t = arr[0]; arr[0] = arr[end]; arr[end] = _t; }
        markSorted(end);
        swap(0, end);
        siftDown(end, 0);
        checkpoint((n - end), n);
    }
    markSorted(0);
} #include <stdio.h>
void siftDown(int size, int root);

void siftDown(int size, int root) {
    while(1) {
        int largest = root;
        int c1 = ((3 * root) + 1);
        int c2 = ((3 * root) + 2);
        int c3 = ((3 * root) + 3);
        if((c1 < size)) {
            compare(c1, largest);
            if((arr[c1] > arr[largest])) {
                largest = c1;
            }
        }
        if((c2 < size)) {
            compare(c2, largest);
            if((arr[c2] > arr[largest])) {
                largest = c2;
            }
        }
        if((c3 < size)) {
            compare(c3, largest);
            if((arr[c3] > arr[largest])) {
                largest = c3;
            }
        }
        if((largest == root)) {
            break;
        }
        { int _t = arr[root]; arr[root] = arr[largest]; arr[largest] = _t; }
        swap(root, largest);
        root = largest;
    }
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    for(int i=((n - 2) / 3); i>(0 - 1); i--) {
        siftDown(n, i);
    }
    for(int end=(n - 1); end>0; end--) {
        { int _t = arr[0]; arr[0] = arr[end]; arr[end] = _t; }
        markSorted(end);
        swap(0, end);
        siftDown(end, 0);
        checkpoint((n - end), n);
    }
    markSorted(0);
} 