Multikey Quicksort

function multikeyQuickSort(arr, stats) {
  const n = arr.length;
  if (n < 2) return;
  let max = arr[0];
  for (let i = 1; i < n; i++) {
    if (arr[i] > max) max = arr[i];
  }
  let maxLen = 1;
  let p = 10;
  while (p <= max) {
    maxLen++;
    p = p * 10;
  }
  const pow = new Array(maxLen).fill(1);
  let e = 1;
  for (let d = maxLen - 1; d >= 0; d--) {
    pow[d] = e;
    e = e * 10;
  }
  const cap = 3 * n + 3 * maxLen + 16;
  const stackLo = new Array(cap).fill(0);
  const stackHi = new Array(cap).fill(0);
  const stackD = new Array(cap).fill(0);
  let top = 0;
  stackLo[top] = 0;
  stackHi[top] = n - 1;
  stackD[top] = 0;
  top++;
  while (top > 0) {
    top--;
    const lo = stackLo[top];
    const hi = stackHi[top];
    const d = stackD[top];
    if (lo >= hi || d >= maxLen) continue;
    const pivot = Math.floor(arr[lo] / pow[d]) % 10;
    let lt = lo;
    let gt = hi;
    let i = lo;
    while (i <= gt) {
      const digit = Math.floor(arr[i] / pow[d]) % 10;
      if (digit < pivot) {
        const t = arr[lt];
        arr[lt] = arr[i];
        arr[i] = t;
        lt++;
        i++;
      } else if (digit > pivot) {
        const t = arr[i];
        arr[i] = arr[gt];
        arr[gt] = t;
        gt--;
      } else {
        i++;
      }
    }
    if (lt - 1 > lo) {
      stackLo[top] = lo;
      stackHi[top] = lt - 1;
      stackD[top] = d;
      top++;
    }
    if (gt > lt && d + 1 < maxLen) {
      stackLo[top] = lt;
      stackHi[top] = gt;
      stackD[top] = d + 1;
      top++;
    }
    if (hi > gt + 1) {
      stackLo[top] = gt + 1;
      stackHi[top] = hi;
      stackD[top] = d;
      top++;
    }
  }
}

def sort(arr, n, stats):
    if (n < 2):
        return
    max = arr[0]
    for i in range(1, n):
        if (arr[i] > max):
            max = arr[i]
    maxLen = 1
    p = 10
    while (p <= max):
        maxLen += 1
        p = (p * 10)
    pow = [1] * maxLen
    e = 1
    for d in range((maxLen - 1), (0 - 1), -1):
        pow[d] = e
        e = (e * 10)
    cap = (((3 * n) + (3 * maxLen)) + 16)
    stackLo = [0] * cap
    stackHi = [0] * cap
    stackD = [0] * cap
    top = 0
    stackLo[top] = 0
    stackHi[top] = (n - 1)
    stackD[top] = 0
    top += 1
    while (top > 0):
        top -= 1
        lo = stackLo[top]
        hi = stackHi[top]
        d = stackD[top]
        if ((lo >= hi) or (d >= maxLen)):
            continue
        pivot = ((arr[lo] // pow[d]) % 10)
        lt = lo
        gt = hi
        i = lo
        while (i <= gt):
            digit = ((arr[i] // pow[d]) % 10)
            if (digit < pivot):
                t = arr[lt]
                arr[lt] = arr[i]
                arr[i] = t
                lt += 1
                i += 1
            elif (digit > pivot):
                t = arr[i]
                arr[i] = arr[gt]
                arr[gt] = t
                gt -= 1
            else:
                i += 1
        if ((lt - 1) > lo):
            stackLo[top] = lo
            stackHi[top] = (lt - 1)
            stackD[top] = d
            top += 1
        if ((gt > lt) and ((d + 1) < maxLen)):
            stackLo[top] = lt
            stackHi[top] = gt
            stackD[top] = (d + 1)
            top += 1
        if (hi > (gt + 1)):
            stackLo[top] = (gt + 1)
            stackHi[top] = hi
            stackD[top] = d
            top += 1

#include <vector>
#include <algorithm>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        return;
    }
    int max = arr[0];
    for(int i=1; i<n; i++) {
        if((arr[i] > max)) {
            max = arr[i];
        }
    }
    int maxLen = 1;
    int p = 10;
    while((p <= max)) {
        maxLen++;
        p = (p * 10);
    }
    std::vector<int> pow(maxLen, 1);
    int e = 1;
    for(int d=(maxLen - 1); d>(0 - 1); d--) {
        pow[d] = e;
        e = (e * 10);
    }
    int cap = (((3 * n) + (3 * maxLen)) + 16);
    std::vector<int> stackLo(cap, 0);
    std::vector<int> stackHi(cap, 0);
    std::vector<int> stackD(cap, 0);
    int top = 0;
    stackLo[top] = 0;
    stackHi[top] = (n - 1);
    stackD[top] = 0;
    top++;
    while((top > 0)) {
        top--;
        int lo = stackLo[top];
        int hi = stackHi[top];
        int d = stackD[top];
        if(((lo >= hi) || (d >= maxLen))) {
            continue;
        }
        int pivot = ((arr[lo] / pow[d]) % 10);
        int lt = lo;
        int gt = hi;
        int i = lo;
        while((i <= gt)) {
            int digit = ((arr[i] / pow[d]) % 10);
            if((digit < pivot)) {
                int t = arr[lt];
                arr[lt] = arr[i];
                arr[i] = t;
                lt++;
                i++;
            } else if((digit > pivot)) {
                int t = arr[i];
                arr[i] = arr[gt];
                arr[gt] = t;
                gt--;
            } else {
                i++;
            }
        }
        if(((lt - 1) > lo)) {
            stackLo[top] = lo;
            stackHi[top] = (lt - 1);
            stackD[top] = d;
            top++;
        }
        if(((gt > lt) && ((d + 1) < maxLen))) {
            stackLo[top] = lt;
            stackHi[top] = gt;
            stackD[top] = (d + 1);
            top++;
        }
        if((hi > (gt + 1))) {
            stackLo[top] = (gt + 1);
            stackHi[top] = hi;
            stackD[top] = d;
            top++;
        }
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        return;
    }
    int max = arr[0];
    for(int i=1; i<n; i++) {
        if((arr[i] > max)) {
            max = arr[i];
        }
    }
    int maxLen = 1;
    int p = 10;
    while((p <= max)) {
        maxLen++;
        p = (p * 10);
    }
    int[] pow = new int[maxLen];
    for(int _i=0;_i<maxLen;_i++) pow[_i]=1;
    int e = 1;
    for(int d=(maxLen - 1); d>(0 - 1); d--) {
        pow[d] = e;
        e = (e * 10);
    }
    int cap = (((3 * n) + (3 * maxLen)) + 16);
    int[] stackLo = new int[cap];
    int[] stackHi = new int[cap];
    int[] stackD = new int[cap];
    int top = 0;
    stackLo[top] = 0;
    stackHi[top] = (n - 1);
    stackD[top] = 0;
    top++;
    while((top > 0)) {
        top--;
        int lo = stackLo[top];
        int hi = stackHi[top];
        int d = stackD[top];
        if(((lo >= hi) || (d >= maxLen))) {
            continue;
        }
        int pivot = ((arr[lo] / pow[d]) % 10);
        int lt = lo;
        int gt = hi;
        int i = lo;
        while((i <= gt)) {
            int digit = ((arr[i] / pow[d]) % 10);
            if((digit < pivot)) {
                int t = arr[lt];
                arr[lt] = arr[i];
                arr[i] = t;
                lt++;
                i++;
            } else if((digit > pivot)) {
                int t = arr[i];
                arr[i] = arr[gt];
                arr[gt] = t;
                gt--;
            } else {
                i++;
            }
        }
        if(((lt - 1) > lo)) {
            stackLo[top] = lo;
            stackHi[top] = (lt - 1);
            stackD[top] = d;
            top++;
        }
        if(((gt > lt) && ((d + 1) < maxLen))) {
            stackLo[top] = lt;
            stackHi[top] = gt;
            stackD[top] = (d + 1);
            top++;
        }
        if((hi > (gt + 1))) {
            stackLo[top] = (gt + 1);
            stackHi[top] = hi;
            stackD[top] = d;
            top++;
        }
    }
}

#include <stdio.h>
#include <string.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        return;
    }
    int max = arr[0];
    for(int i=1; i<n; i++) {
        if((arr[i] > max)) {
            max = arr[i];
        }
    }
    int maxLen = 1;
    int p = 10;
    while((p <= max)) {
        maxLen++;
        p = (p * 10);
    }
    int pow[maxLen]; for(int _i=0;_i<maxLen;_i++) pow[_i]=1;
    int e = 1;
    for(int d=(maxLen - 1); d>(0 - 1); d--) {
        pow[d] = e;
        e = (e * 10);
    }
    int cap = (((3 * n) + (3 * maxLen)) + 16);
    int stackLo[cap]; memset(stackLo, 0, sizeof(stackLo));
    int stackHi[cap]; memset(stackHi, 0, sizeof(stackHi));
    int stackD[cap]; memset(stackD, 0, sizeof(stackD));
    int top = 0;
    stackLo[top] = 0;
    stackHi[top] = (n - 1);
    stackD[top] = 0;
    top++;
    while((top > 0)) {
        top--;
        int lo = stackLo[top];
        int hi = stackHi[top];
        int d = stackD[top];
        if(((lo >= hi) || (d >= maxLen))) {
            continue;
        }
        int pivot = ((arr[lo] / pow[d]) % 10);
        int lt = lo;
        int gt = hi;
        int i = lo;
        while((i <= gt)) {
            int digit = ((arr[i] / pow[d]) % 10);
            if((digit < pivot)) {
                int t = arr[lt];
                arr[lt] = arr[i];
                arr[i] = t;
                lt++;
                i++;
            } else if((digit > pivot)) {
                int t = arr[i];
                arr[i] = arr[gt];
                arr[gt] = t;
                gt--;
            } else {
                i++;
            }
        }
        if(((lt - 1) > lo)) {
            stackLo[top] = lo;
            stackHi[top] = (lt - 1);
            stackD[top] = d;
            top++;
        }
        if(((gt > lt) && ((d + 1) < maxLen))) {
            stackLo[top] = lt;
            stackHi[top] = gt;
            stackD[top] = (d + 1);
            top++;
        }
        if((hi > (gt + 1))) {
            stackLo[top] = (gt + 1);
            stackHi[top] = hi;
            stackD[top] = d;
            top++;
        }
    }
}