American Flag Sort

function americanFlagSort(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];
  }
  const RADIX = 16;
  let topExp = 1;
  while (Math.floor(max / topExp) >= RADIX) {
    topExp = topExp * RADIX;
  }
  const stackLo = new Array(n + 32).fill(0);
  const stackHi = new Array(n + 32).fill(0);
  const stackExp = new Array(n + 32).fill(0);
  const count = new Array(RADIX).fill(0);
  const start = new Array(RADIX).fill(0);
  const next = new Array(RADIX).fill(0);
  let top = 0;
  stackLo[top] = 0;
  stackHi[top] = n;
  stackExp[top] = topExp;
  top++;
  while (top > 0) {
    top--;
    const lo = stackLo[top];
    const hi = stackHi[top];
    const e = stackExp[top];
    if (hi - lo <= 1 || e === 0) continue;
    for (let d = 0; d < RADIX; d++) {
      count[d] = 0;
    }
    for (let i = lo; i < hi; i++) {
      const digit = Math.floor(arr[i] / e) % RADIX;
      count[digit]++;
    }
    let sum = lo;
    for (let d = 0; d < RADIX; d++) {
      start[d] = sum;
      next[d] = sum;
      sum = sum + count[d];
    }
    for (let b = 0; b < RADIX; b++) {
      const end = start[b] + count[b];
      while (next[b] < end) {
        const i = next[b];
        const digit = Math.floor(arr[i] / e) % RADIX;
        if (digit === b) {
          next[b]++;
        } else {
          const to = next[digit];
          const t = arr[i];
          arr[i] = arr[to];
          arr[to] = t;
          next[digit]++;
        }
      }
    }
    if (e > 1) {
      for (let b = 0; b < RADIX; b++) {
        if (count[b] > 1) {
          stackLo[top] = start[b];
          stackHi[top] = start[b] + count[b];
          stackExp[top] = Math.floor(e / RADIX);
          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]
    RADIX = 16
    topExp = 1
    while ((max // topExp) >= RADIX):
        topExp = (topExp * RADIX)
    stackLo = [0] * (n + 32)
    stackHi = [0] * (n + 32)
    stackExp = [0] * (n + 32)
    count = [0] * RADIX
    start = [0] * RADIX
    next = [0] * RADIX
    top = 0
    stackLo[top] = 0
    stackHi[top] = n
    stackExp[top] = topExp
    top += 1
    while (top > 0):
        top -= 1
        lo = stackLo[top]
        hi = stackHi[top]
        e = stackExp[top]
        if (((hi - lo) <= 1) or (e == 0)):
            continue
        for d in range(RADIX):
            count[d] = 0
        for i in range(lo, hi):
            digit = ((arr[i] // e) % RADIX)
            count[digit] += 1
        sum = lo
        for d in range(RADIX):
            start[d] = sum
            next[d] = sum
            sum = (sum + count[d])
        for b in range(RADIX):
            end = (start[b] + count[b])
            while (next[b] < end):
                i = next[b]
                digit = ((arr[i] // e) % RADIX)
                if (digit == b):
                    next[b] += 1
                else:
                    to = next[digit]
                    t = arr[i]
                    arr[i] = arr[to]
                    arr[to] = t
                    next[digit] += 1
        if (e > 1):
            for b in range(RADIX):
                if (count[b] > 1):
                    stackLo[top] = start[b]
                    stackHi[top] = (start[b] + count[b])
                    stackExp[top] = (e // RADIX)
                    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 RADIX = 16;
    int topExp = 1;
    while(((max / topExp) >= RADIX)) {
        topExp = (topExp * RADIX);
    }
    std::vector<int> stackLo((n + 32), 0);
    std::vector<int> stackHi((n + 32), 0);
    std::vector<int> stackExp((n + 32), 0);
    std::vector<int> count(RADIX, 0);
    std::vector<int> start(RADIX, 0);
    std::vector<int> next(RADIX, 0);
    int top = 0;
    stackLo[top] = 0;
    stackHi[top] = n;
    stackExp[top] = topExp;
    top++;
    while((top > 0)) {
        top--;
        int lo = stackLo[top];
        int hi = stackHi[top];
        int e = stackExp[top];
        if((((hi - lo) <= 1) || (e == 0))) {
            continue;
        }
        for(int d=0; d<RADIX; d++) {
            count[d] = 0;
        }
        for(int i=lo; i<hi; i++) {
            int digit = ((arr[i] / e) % RADIX);
            count[digit]++;
        }
        int sum = lo;
        for(int d=0; d<RADIX; d++) {
            start[d] = sum;
            next[d] = sum;
            sum = (sum + count[d]);
        }
        for(int b=0; b<RADIX; b++) {
            int end = (start[b] + count[b]);
            while((next[b] < end)) {
                int i = next[b];
                int digit = ((arr[i] / e) % RADIX);
                if((digit == b)) {
                    next[b]++;
                } else {
                    int to = next[digit];
                    int t = arr[i];
                    arr[i] = arr[to];
                    arr[to] = t;
                    next[digit]++;
                }
            }
        }
        if((e > 1)) {
            for(int b=0; b<RADIX; b++) {
                if((count[b] > 1)) {
                    stackLo[top] = start[b];
                    stackHi[top] = (start[b] + count[b]);
                    stackExp[top] = (e / RADIX);
                    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 RADIX = 16;
    int topExp = 1;
    while(((max / topExp) >= RADIX)) {
        topExp = (topExp * RADIX);
    }
    int[] stackLo = new int[(n + 32)];
    int[] stackHi = new int[(n + 32)];
    int[] stackExp = new int[(n + 32)];
    int[] count = new int[RADIX];
    int[] start = new int[RADIX];
    int[] next = new int[RADIX];
    int top = 0;
    stackLo[top] = 0;
    stackHi[top] = n;
    stackExp[top] = topExp;
    top++;
    while((top > 0)) {
        top--;
        int lo = stackLo[top];
        int hi = stackHi[top];
        int e = stackExp[top];
        if((((hi - lo) <= 1) || (e == 0))) {
            continue;
        }
        for(int d=0; d<RADIX; d++) {
            count[d] = 0;
        }
        for(int i=lo; i<hi; i++) {
            int digit = ((arr[i] / e) % RADIX);
            count[digit]++;
        }
        int sum = lo;
        for(int d=0; d<RADIX; d++) {
            start[d] = sum;
            next[d] = sum;
            sum = (sum + count[d]);
        }
        for(int b=0; b<RADIX; b++) {
            int end = (start[b] + count[b]);
            while((next[b] < end)) {
                int i = next[b];
                int digit = ((arr[i] / e) % RADIX);
                if((digit == b)) {
                    next[b]++;
                } else {
                    int to = next[digit];
                    int t = arr[i];
                    arr[i] = arr[to];
                    arr[to] = t;
                    next[digit]++;
                }
            }
        }
        if((e > 1)) {
            for(int b=0; b<RADIX; b++) {
                if((count[b] > 1)) {
                    stackLo[top] = start[b];
                    stackHi[top] = (start[b] + count[b]);
                    stackExp[top] = (e / RADIX);
                    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 RADIX = 16;
    int topExp = 1;
    while(((max / topExp) >= RADIX)) {
        topExp = (topExp * RADIX);
    }
    int stackLo[(n + 32)]; memset(stackLo, 0, sizeof(stackLo));
    int stackHi[(n + 32)]; memset(stackHi, 0, sizeof(stackHi));
    int stackExp[(n + 32)]; memset(stackExp, 0, sizeof(stackExp));
    int count[RADIX]; memset(count, 0, sizeof(count));
    int start[RADIX]; memset(start, 0, sizeof(start));
    int next[RADIX]; memset(next, 0, sizeof(next));
    int top = 0;
    stackLo[top] = 0;
    stackHi[top] = n;
    stackExp[top] = topExp;
    top++;
    while((top > 0)) {
        top--;
        int lo = stackLo[top];
        int hi = stackHi[top];
        int e = stackExp[top];
        if((((hi - lo) <= 1) || (e == 0))) {
            continue;
        }
        for(int d=0; d<RADIX; d++) {
            count[d] = 0;
        }
        for(int i=lo; i<hi; i++) {
            int digit = ((arr[i] / e) % RADIX);
            count[digit]++;
        }
        int sum = lo;
        for(int d=0; d<RADIX; d++) {
            start[d] = sum;
            next[d] = sum;
            sum = (sum + count[d]);
        }
        for(int b=0; b<RADIX; b++) {
            int end = (start[b] + count[b]);
            while((next[b] < end)) {
                int i = next[b];
                int digit = ((arr[i] / e) % RADIX);
                if((digit == b)) {
                    next[b]++;
                } else {
                    int to = next[digit];
                    int t = arr[i];
                    arr[i] = arr[to];
                    arr[to] = t;
                    next[digit]++;
                }
            }
        }
        if((e > 1)) {
            for(int b=0; b<RADIX; b++) {
                if((count[b] > 1)) {
                    stackLo[top] = start[b];
                    stackHi[top] = (start[b] + count[b]);
                    stackExp[top] = (e / RADIX);
                    top++;
                }
            }
        }
    }
}