American Flag Sort

function americanFlagSort(arr, stats) {
  if (arr.length < 2) return;
  let max = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  const RADIX = 256;
  let exp = 1;
  while (Math.floor(max / exp) >= RADIX) exp *= RADIX;
  function sortRange(lo, hi, e) {
    if (hi - lo <= 1 || e === 0) return;
    const count = new Array(RADIX).fill(0);
    for (let i = lo; i < hi; i++) {
      const d = Math.floor(arr[i] / e) % RADIX;
      count[d]++;
    }
    const start = new Array(RADIX).fill(0);
    const next = new Array(RADIX).fill(0);
    let sum = lo;
    for (let i = 0; i < RADIX; i++) {
      start[i] = sum;
      next[i] = sum;
      sum += count[i];
    }
    for (let b = 0; b < RADIX; b++) {
      let i = next[b];
      const end = start[b] + count[b];
      while (i < end) {
        const d = Math.floor(arr[i] / e) % RADIX;
        if (d === b) {
          i++;
        } else {
          const to = next[d]++;
          swap(i, to);
          const t = arr[i];
          arr[i] = arr[to];
          arr[to] = t;
        }
      }
    }
    if (e > 1) {
      for (let b = 0; b < RADIX; b++) {
        if (count[b] > 1) sortRange(start[b], start[b] + count[b], Math.floor(e / RADIX));
      }
    }
  }
  sortRange(0, arr.length, exp);
}

def sort(arr, n, stats):
    if (len(arr) < 2):
        return
    max = 0
    for i in range(len(arr)):
        if (arr[i] > max):
            max = arr[i]
    RADIX = 256
    exp = 1
    while ((max // exp) >= RADIX):
        exp *= RADIX
    def sortRange(lo, hi, e):
        if (((hi - lo) <= 1) or (e == 0)):
            return
        count = [0] * RADIX
        for i in range(lo, hi):
            d = ((arr[i] // e) % RADIX)
            count[d] += 1
        start = [0] * RADIX
        next = [0] * RADIX
        sum = lo
        for i in range(RADIX):
            start[i] = sum
            next[i] = sum
            sum += count[i]
        for b in range(RADIX):
            i = next[b]
            end = (start[b] + count[b])
            while (i < end):
                d = ((arr[i] // e) % RADIX)
                if (d == b):
                    i += 1
                else:
                    to = next[d] += 1
                    t = arr[i]
                    arr[i] = arr[to]
                    arr[to] = t
        if (e > 1):
            for b in range(RADIX):
                if (count[b] > 1):
                    sortRange(start[b], (start[b] + count[b]), (e // RADIX))
    sortRange(0, len(arr), exp)

#include <vector>
#include <algorithm>
#include <cstring>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    void sortRange(int lo, int hi, int e) {
        if((((hi - lo) <= 1) || (e == 0))) {
            return;
        }
        std::vector<int> count(RADIX); std::memset(count, 0, sizeof(count));
        for(int i=lo; (i < hi); i++) {
            int d = ((arr[i] / e) % RADIX);
            count[d]++;
        }
        std::vector<int> start(RADIX); std::memset(start, 0, sizeof(start));
        std::vector<int> next(RADIX); std::memset(next, 0, sizeof(next));
        int sum = lo;
        for(int i=0; (i < RADIX); i++) {
            start[i] = sum;
            next[i] = sum;
            sum += count[i];
        }
        for(int b=0; (b < RADIX); b++) {
            int i = next[b];
            int end = (start[b] + count[b]);
            while((i < end)) {
                int d = ((arr[i] / e) % RADIX);
                if((d == b)) {
                    i++;
                } else {
                    int to = next[d]++;
                    int t = arr[i];
                    arr[i] = arr[to];
                    arr[to] = t;
                }
            }
        }
        if((e > 1)) {
            for(int b=0; (b < RADIX); b++) {
                if((count[b] > 1)) {
                    sortRange(start[b], (start[b] + count[b]), (e / RADIX));
                }
            }
        }
    }
    if((n < 2)) {
        return;
    }
    int max = 0;
    for(int i=0; (i < n); i++) {
        if((arr[i] > max)) {
            max = arr[i];
        }
    }
    int RADIX = 256;
    int exp = 1;
    while(((max / exp) >= RADIX)) {
        exp *= RADIX;
    }
    sortRange(0, n, exp);
}

public void Sort(int[] arr, int n, dynamic stats) {
    void sortRange(int lo, int hi, int e) {
        if((((hi - lo) <= 1) || (e == 0))) {
            return;
        }
        int[] count = new int[RADIX]; Array.Clear(count, 0, sizeof(count));
        for(int i=lo; (i < hi); i++) {
            int d = ((arr[i] / e) % RADIX);
            count[d]++;
        }
        int[] start = new int[RADIX]; Array.Clear(start, 0, sizeof(start));
        int[] next = new int[RADIX]; Array.Clear(next, 0, sizeof(next));
        int sum = lo;
        for(int i=0; (i < RADIX); i++) {
            start[i] = sum;
            next[i] = sum;
            sum += count[i];
        }
        for(int b=0; (b < RADIX); b++) {
            int i = next[b];
            int end = (start[b] + count[b]);
            while((i < end)) {
                int d = ((arr[i] / e) % RADIX);
                if((d == b)) {
                    i++;
                } else {
                    int to = next[d]++;
                    int t = arr[i];
                    arr[i] = arr[to];
                    arr[to] = t;
                }
            }
        }
        if((e > 1)) {
            for(int b=0; (b < RADIX); b++) {
                if((count[b] > 1)) {
                    sortRange(start[b], (start[b] + count[b]), (e / RADIX));
                }
            }
        }
    }
    if((n < 2)) {
        return;
    }
    int max = 0;
    for(int i=0; (i < n); i++) {
        if((arr[i] > max)) {
            max = arr[i];
        }
    }
    int RADIX = 256;
    int exp = 1;
    while(((max / exp) >= RADIX)) {
        exp *= RADIX;
    }
    sortRange(0, n, exp);
}

#include <stdio.h>
#include <string.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    void sortRange(int lo, int hi, int e) {
        if((((hi - lo) <= 1) || (e == 0))) {
            return;
        }
        int count[RADIX]; memset(count, 0, sizeof(count));
        for(int i=lo; (i < hi); i++) {
            int d = ((arr[i] / e) % RADIX);
            count[d]++;
        }
        int start[RADIX]; memset(start, 0, sizeof(start));
        int next[RADIX]; memset(next, 0, sizeof(next));
        int sum = lo;
        for(int i=0; (i < RADIX); i++) {
            start[i] = sum;
            next[i] = sum;
            sum += count[i];
        }
        for(int b=0; (b < RADIX); b++) {
            int i = next[b];
            int end = (start[b] + count[b]);
            while((i < end)) {
                int d = ((arr[i] / e) % RADIX);
                if((d == b)) {
                    i++;
                } else {
                    int to = next[d]++;
                    int t = arr[i];
                    arr[i] = arr[to];
                    arr[to] = t;
                }
            }
        }
        if((e > 1)) {
            for(int b=0; (b < RADIX); b++) {
                if((count[b] > 1)) {
                    sortRange(start[b], (start[b] + count[b]), (e / RADIX));
                }
            }
        }
    }
    if((n < 2)) {
        return;
    }
    int max = 0;
    for(int i=0; (i < n); i++) {
        if((arr[i] > max)) {
            max = arr[i];
        }
    }
    int RADIX = 256;
    int exp = 1;
    while(((max / exp) >= RADIX)) {
        exp *= RADIX;
    }
    sortRange(0, n, exp);
}