American Flag Sort

pick a language to open the code

def flag_sort(a, lo, hi, exp):
    if exp == 0 or hi - lo < 2:
        return
    count = [0] * 10
    for i in range(lo, hi):
        count[a[i] // exp % 10] += 1
    starts = [lo] * 10
    for d in range(1, 10):
        starts[d] = starts[d - 1] + count[d - 1]
    heads = list(starts)
    for d in range(10):
        while heads[d] < starts[d] + count[d]:
            value = a[heads[d]]
            k = value // exp % 10
            while k != d:
                value, a[heads[k]] = a[heads[k]], value
                heads[k] += 1
                k = value // exp % 10
            a[heads[d]] = value
            heads[d] += 1
    for d in range(10):
        flag_sort(a, starts[d], starts[d] + count[d], exp // 10)


def american_flag_sort(a):
    exp = 1
    while a and max(a) // exp >= 10:
        exp *= 10
    flag_sort(a, 0, len(a), exp)

function flagSort(a, lo, hi, exp) {
  if (exp === 0 || hi - lo < 2) return;
  const count = new Array(10).fill(0);
  for (let i = lo; i < hi; i++) count[Math.floor(a[i] / exp) % 10]++;
  const starts = new Array(10).fill(lo);
  for (let d = 1; d < 10; d++) starts[d] = starts[d - 1] + count[d - 1];
  const heads = starts.slice();
  for (let d = 0; d < 10; d++) {
    while (heads[d] < starts[d] + count[d]) {
      let value = a[heads[d]];
      let k = Math.floor(value / exp) % 10;
      while (k !== d) {
        [value, a[heads[k]]] = [a[heads[k]], value];
        heads[k]++;
        k = Math.floor(value / exp) % 10;
      }
      a[heads[d]++] = value;
    }
  }
  for (let d = 0; d < 10; d++) {
    flagSort(a, starts[d], starts[d] + count[d], Math.floor(exp / 10));
  }
}

function americanFlagSort(a) {
  if (a.length === 0) return;
  const top = Math.max(...a);
  let exp = 1;
  while (top / exp >= 10) exp *= 10;
  flagSort(a, 0, a.length, exp);
}

static void flag_sort(int a[], int lo, int hi, int exp) {
    if (exp == 0 || hi - lo < 2) return;
    int count[10] = {0};
    for (int i = lo; i < hi; i++) count[a[i] / exp % 10]++;
    int starts[10], heads[10];
    starts[0] = lo;
    for (int d = 1; d < 10; d++) starts[d] = starts[d - 1] + count[d - 1];
    for (int d = 0; d < 10; d++) heads[d] = starts[d];
    for (int d = 0; d < 10; d++) {
        while (heads[d] < starts[d] + count[d]) {
            int value = a[heads[d]];
            int k = value / exp % 10;
            while (k != d) {
                int hold = a[heads[k]];
                a[heads[k]++] = value;
                value = hold;
                k = value / exp % 10;
            }
            a[heads[d]++] = value;
        }
    }
    for (int d = 0; d < 10; d++) {
        flag_sort(a, starts[d], starts[d] + count[d], exp / 10);
    }
}

void american_flag_sort(int a[], int n) {
    int top = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > top) top = a[i];
    }
    int exp = 1;
    while (top / exp >= 10) exp *= 10;
    flag_sort(a, 0, n, exp);
}

static void flag_sort(std::vector<int>& a, int lo, int hi, int exp) {
    if (exp == 0 || hi - lo < 2) return;
    std::array<int, 10> count{};
    for (int i = lo; i < hi; i++) count[a[i] / exp % 10]++;
    std::array<int, 10> starts{};
    starts[0] = lo;
    for (int d = 1; d < 10; d++) starts[d] = starts[d - 1] + count[d - 1];
    std::array<int, 10> heads = starts;
    for (int d = 0; d < 10; d++) {
        while (heads[d] < starts[d] + count[d]) {
            int value = a[heads[d]];
            int k = value / exp % 10;
            while (k != d) {
                std::swap(value, a[heads[k]++]);
                k = value / exp % 10;
            }
            a[heads[d]++] = value;
        }
    }
    for (int d = 0; d < 10; d++) {
        flag_sort(a, starts[d], starts[d] + count[d], exp / 10);
    }
}

void american_flag_sort(std::vector<int>& a) {
    if (a.empty()) return;
    int top = *std::max_element(a.begin(), a.end());
    int exp = 1;
    while (top / exp >= 10) exp *= 10;
    flag_sort(a, 0, static_cast<int>(a.size()), exp);
}

static void FlagSort(int[] a, int lo, int hi, int exp) {
    if (exp == 0 || hi - lo < 2) return;
    int[] count = new int[10];
    for (int i = lo; i < hi; i++) count[a[i] / exp % 10]++;
    int[] starts = new int[10];
    starts[0] = lo;
    for (int d = 1; d < 10; d++) starts[d] = starts[d - 1] + count[d - 1];
    int[] heads = (int[])starts.Clone();
    for (int d = 0; d < 10; d++) {
        while (heads[d] < starts[d] + count[d]) {
            int value = a[heads[d]];
            int k = value / exp % 10;
            while (k != d) {
                (value, a[heads[k]]) = (a[heads[k]], value);
                heads[k]++;
                k = value / exp % 10;
            }
            a[heads[d]++] = value;
        }
    }
    for (int d = 0; d < 10; d++) {
        FlagSort(a, starts[d], starts[d] + count[d], exp / 10);
    }
}

static void AmericanFlagSort(int[] a) {
    if (a.Length == 0) return;
    int top = a.Max();
    int exp = 1;
    while (top / exp >= 10) exp *= 10;
    FlagSort(a, 0, a.Length, exp);
}

static void flagSort(int[] a, int lo, int hi, int exp) {
    if (exp == 0 || hi - lo < 2) return;
    int[] count = new int[10];
    for (int i = lo; i < hi; i++) count[a[i] / exp % 10]++;
    int[] starts = new int[10];
    starts[0] = lo;
    for (int d = 1; d < 10; d++) starts[d] = starts[d - 1] + count[d - 1];
    int[] heads = starts.clone();
    for (int d = 0; d < 10; d++) {
        while (heads[d] < starts[d] + count[d]) {
            int value = a[heads[d]];
            int k = value / exp % 10;
            while (k != d) {
                int hold = a[heads[k]];
                a[heads[k]++] = value;
                value = hold;
                k = value / exp % 10;
            }
            a[heads[d]++] = value;
        }
    }
    for (int d = 0; d < 10; d++) {
        flagSort(a, starts[d], starts[d] + count[d], exp / 10);
    }
}

static void americanFlagSort(int[] a) {
    if (a.length == 0) return;
    int top = Arrays.stream(a).max().getAsInt();
    int exp = 1;
    while (top / exp >= 10) exp *= 10;
    flagSort(a, 0, a.length, exp);
}