Multikey Quicksort — VisualAlgorithms Docs

How it works

3-way radix quicksort: partitions on one key symbol at a time (here, decimal digits from most significant to least), recursing deeper only on the equal-digit middle. Ideal for keys built from a small alphabet.
Implementation

      
 function multikeyQuickSort(arr, stats) {
  const n = arr.length;
  if (n < 2) return;
  let maxVal = 0;
  for (let i = 0; i < n; i++) {
    if (arr[i] > maxVal) maxVal = arr[i];
  }
  let maxDigits = 1;
  let remaining = maxVal;
  while (remaining >= 10) {
    remaining = Math.floor(remaining / 10);
    maxDigits++;
  }
  function digitAt(v, d) {
    const power = maxDigits - 1 - d;
    let divisor = 1;
    for (let k = 0; k < power; k++) divisor = divisor * 10;
    return Math.floor(v / divisor) % 10;
  }
  function sort(lo, hi, d) {
    if (lo >= hi || d >= maxDigits) return;
    let lt = lo;
    let gt = hi;
    let i = lo + 1;
    const pivot = digitAt(arr[lo], d);
    while (i <= gt) {
      const code = digitAt(arr[i], d);
      compare(i, lo);
      if (code < pivot) {
        [arr[lt], arr[i]] = [arr[i], arr[lt]];
        swap(lt, i);
        lt++;
        i++;
      } else if (code > pivot) {
        [arr[i], arr[gt]] = [arr[gt], arr[i]];
        swap(i, gt);
        gt--;
      } else {
        i++;
      }
    }
    sort(lo, lt - 1, d);
    sort(lt, gt, d + 1);
    sort(gt + 1, hi, d);
  }
  sort(0, n - 1, 0);
  for (let i = 0; i < n; i++) markSorted(i);
}
 def multikeyQuickSort(arr, stats):
    def digitAt(v, d):
        power = ((maxDigits - 1) - d)
        divisor = 1
        for k in range(power):
            divisor = (divisor * 10)
        return (int(v / divisor) % 10)

    def sort(lo, hi, d):
        if ((lo >= hi) or (d >= maxDigits)):
            return
        lt = lo
        gt = hi
        i = (lo + 1)
        pivot = digitAt(arr[lo], d)
        while (i <= gt):
            code = digitAt(arr[i], d)
            compare(i, lo)
            if (code < pivot):
                arr[lt], arr[i] = arr[i], arr[lt]
                swap(lt, i)
                lt += 1
                i += 1
            elif (code > pivot):
                arr[i], arr[gt] = arr[gt], arr[i]
                swap(i, gt)
                gt -= 1
            else:
                i += 1
        sort(lo, (lt - 1), d)
        sort(lt, gt, (d + 1))
        sort((gt + 1), hi, d)

    if (n < 2):
        return
    maxVal = 0
    for i in range(n):
        if (arr[i] > maxVal):
            maxVal = arr[i]
    maxDigits = 1
    remaining = maxVal
    while (remaining >= 10):
        remaining = (remaining // 10)
        maxDigits += 1
    sort(0, (n - 1), 0)
    for i in range(n):
        markSorted(i)
 #include <vector>
#include <algorithm>
int digitAt(int v, int d);
void sort(int lo, int hi, int d);

int digitAt(int v, int d) {
    int power = ((maxDigits - 1) - d);
    int divisor = 1;
    for(int k=0; k<power; k++) {
        divisor = (divisor * 10);
    }
    return ((v / divisor) % 10);
}

void sort(int lo, int hi, int d) {
    if(((lo >= hi) || (d >= maxDigits))) {
        return;
    }
    int lt = lo;
    int gt = hi;
    int i = (lo + 1);
    int pivot = digitAt(arr[lo], d);
    while((i <= gt)) {
        int code = digitAt(arr[i], d);
        compare(i, lo);
        if((code < pivot)) {
            std::swap(arr[lt], arr[i]);
            swap(lt, i);
            lt++;
            i++;
        } else if((code > pivot)) {
            std::swap(arr[i], arr[gt]);
            swap(i, gt);
            gt--;
        } else {
            i++;
        }
    }
    sort(lo, (lt - 1), d);
    sort(lt, gt, (d + 1));
    sort((gt + 1), hi, d);
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        return;
    }
    int maxVal = 0;
    for(int i=0; i<n; i++) {
        if((arr[i] > maxVal)) {
            maxVal = arr[i];
        }
    }
    int maxDigits = 1;
    int remaining = maxVal;
    while((remaining >= 10)) {
        remaining = (remaining / 10);
        maxDigits++;
    }
    sort(0, (n - 1), 0);
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} int digitAt(int v, int d) {
    int power = ((maxDigits - 1) - d);
    int divisor = 1;
    for(int k=0; k<power; k++) {
        divisor = (divisor * 10);
    }
    return ((v / divisor) % 10);
}

void sort(int lo, int hi, int d) {
    if(((lo >= hi) || (d >= maxDigits))) {
        return;
    }
    int lt = lo;
    int gt = hi;
    int i = (lo + 1);
    int pivot = digitAt(arr[lo], d);
    while((i <= gt)) {
        int code = digitAt(arr[i], d);
        compare(i, lo);
        if((code < pivot)) {
            { int _t = arr[lt]; arr[lt] = arr[i]; arr[i] = _t; }
            swap(lt, i);
            lt++;
            i++;
        } else if((code > pivot)) {
            { int _t = arr[i]; arr[i] = arr[gt]; arr[gt] = _t; }
            swap(i, gt);
            gt--;
        } else {
            i++;
        }
    }
    sort(lo, (lt - 1), d);
    sort(lt, gt, (d + 1));
    sort((gt + 1), hi, d);
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        return;
    }
    int maxVal = 0;
    for(int i=0; i<n; i++) {
        if((arr[i] > maxVal)) {
            maxVal = arr[i];
        }
    }
    int maxDigits = 1;
    int remaining = maxVal;
    while((remaining >= 10)) {
        remaining = (remaining / 10);
        maxDigits++;
    }
    sort(0, (n - 1), 0);
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} #include <stdio.h>
int digitAt(int v, int d);
void sort(int lo, int hi, int d);

int digitAt(int v, int d) {
    int power = ((maxDigits - 1) - d);
    int divisor = 1;
    for(int k=0; k<power; k++) {
        divisor = (divisor * 10);
    }
    return ((v / divisor) % 10);
}

void sort(int lo, int hi, int d) {
    if(((lo >= hi) || (d >= maxDigits))) {
        return;
    }
    int lt = lo;
    int gt = hi;
    int i = (lo + 1);
    int pivot = digitAt(arr[lo], d);
    while((i <= gt)) {
        int code = digitAt(arr[i], d);
        compare(i, lo);
        if((code < pivot)) {
            { int _t = arr[lt]; arr[lt] = arr[i]; arr[i] = _t; }
            swap(lt, i);
            lt++;
            i++;
        } else if((code > pivot)) {
            { int _t = arr[i]; arr[i] = arr[gt]; arr[gt] = _t; }
            swap(i, gt);
            gt--;
        } else {
            i++;
        }
    }
    sort(lo, (lt - 1), d);
    sort(lt, gt, (d + 1));
    sort((gt + 1), hi, d);
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        return;
    }
    int maxVal = 0;
    for(int i=0; i<n; i++) {
        if((arr[i] > maxVal)) {
            maxVal = arr[i];
        }
    }
    int maxDigits = 1;
    int remaining = maxVal;
    while((remaining >= 10)) {
        remaining = (remaining / 10);
        maxDigits++;
    }
    sort(0, (n - 1), 0);
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} 