American Flag Sort

function americanFlagSort(arr, stats) {
  if (arr.length < 2) return;
  const metrics = stats.educational.metrics;
  const recordMetric = (name, delta = 1) => {
    metrics[name] = (metrics[name] || 0) + delta;
  };
  let min = arr[0];
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < min) min = arr[i];
    if (arr[i] > max) max = arr[i];
  }
  const RADIX = 256;
  const offset = min < 0 ? -min : 0;
  const maxKey = max + offset;
  metrics.radixBase = RADIX;
  metrics.signedOffset = offset;
  let divisor = 1;
  while (Math.floor(maxKey / divisor) >= RADIX) divisor *= RADIX;
  function digitFor(value, currentDivisor) {
    recordMetric('digitExtractions');
    return Math.floor((value + offset) / currentDivisor) % RADIX;
  }
  function sortRange(lo, hi, currentDivisor) {
    if (hi - lo <= 1 || currentDivisor === 0) {
      if (hi - lo === 1) markSorted(lo);
      return;
    }
    recordMetric('distributionPasses');
    const count = new Array(RADIX).fill(0);
    for (let i = lo; i < hi; i++) {
      const d = digitFor(arr[i], currentDivisor);
      count[d]++;
      recordMetric('countArrayWrites');
    }
    const start = new Array(RADIX).fill(0);
    const end = 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];
      end[i] = sum;
    }
    for (let b = 0; b < RADIX; b++) {
      let i = next[b];
      while (i < end[b]) {
        const d = digitFor(arr[i], currentDivisor);
        recordMetric('bucketScans');
        if (d === b) {
          i++;
        } else {
          const to = next[d]++;
          swap(i, to);
          const t = arr[i];
          arr[i] = arr[to];
          arr[to] = t;
          recordMetric('cycleMoves');
        }
      }
    }
    if (currentDivisor === 1) {
      for (let b = 0; b < RADIX; b++) {
        if (count[b] > 0) {
          for (let i = start[b]; i < end[b]; i++) markSorted(i);
        }
      }
    } else {
      const nextDivisor = Math.floor(currentDivisor / RADIX);
      for (let b = 0; b < RADIX; b++) {
        if (count[b] > 1) {
          recordMetric('recursiveBuckets');
          sortRange(start[b], end[b], nextDivisor);
        } else if (count[b] === 1) {
          markSorted(start[b]);
        }
      }
    }
    checkpoint(Math.min(hi, arr.length), arr.length);
  }
  sortRange(0, arr.length, divisor);
}

def americanFlagSort(arr, stats):
    def recordMetric(name, ):
        metrics[name] = ((metrics[name] or 0) + delta)

    def digitFor(value, currentDivisor):
        recordMetric("digitExtractions")
        return (int((value + offset) / currentDivisor) % RADIX)

    def sortRange(lo, hi, currentDivisor):
        if (((hi - lo) <= 1) or (currentDivisor == 0)):
            if ((hi - lo) == 1):
                markSorted(lo)
            return
        recordMetric("distributionPasses")
        count = [0] * RADIX
        for i in range(lo, hi):
            d = digitFor(arr[i], currentDivisor)
            count[d] += 1
            recordMetric("countArrayWrites")
        start = [0] * RADIX
        end = [0] * RADIX
        next = [0] * RADIX
        sum = lo
        for i in range(RADIX):
            start[i] = sum
            next[i] = sum
            sum += count[i]
            end[i] = sum
        for b in range(RADIX):
            i = next[b]
            while (i < end[b]):
                d = digitFor(arr[i], currentDivisor)
                recordMetric("bucketScans")
                if (d == b):
                    i += 1
                else:
                    to = next[d]
                    swap(i, to)
                    t = arr[i]
                    arr[i] = arr[to]
                    arr[to] = t
                    recordMetric("cycleMoves")
        if (currentDivisor == 1):
            for b in range(RADIX):
                if (count[b] > 0):
                    for i in range(start[b], end[b]):
                        markSorted(i)
        else:
            nextDivisor = int(currentDivisor / RADIX)
            for b in range(RADIX):
                if (count[b] > 1):
                    recordMetric("recursiveBuckets")
                    sortRange(start[b], end[b], nextDivisor)
                elif (count[b] == 1):
                    markSorted(start[b])
        checkpoint((hi if hi <= len(arr) else len(arr)), len(arr))

    if (len(arr) < 2):
        return
    min = arr[0]
    max = arr[0]
    for i in range(1, len(arr)):
        if (arr[i] < min):
            min = arr[i]
        if (arr[i] > max):
            max = arr[i]
    RADIX = 256
    offset = (-min if (min < 0) else 0)
    maxKey = (max + offset)
    metrics.radixBase = RADIX
    metrics.signedOffset = offset
    divisor = 1
    while (int(maxKey / divisor) >= RADIX):
        divisor *= RADIX
    sortRange(0, len(arr), divisor)

#include <vector>
#include <algorithm>
void recordMetric(int name, int );
int digitFor(int value, int currentDivisor);
void sortRange(int lo, int hi, int currentDivisor);

void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

int digitFor(int value, int currentDivisor) {
    recordMetric("digitExtractions");
    return (((value + offset) / currentDivisor) % RADIX);
}

void sortRange(int lo, int hi, int currentDivisor) {
    if((((hi - lo) <= 1) || (currentDivisor == 0))) {
        if(((hi - lo) == 1)) {
            markSorted(lo);
        }
        return;
    }
    recordMetric("distributionPasses");
    std::vector<int> count(RADIX, 0);
    for(int i=lo; i<hi; i++) {
        int d = digitFor(arr[i], currentDivisor);
        count[d]++;
        recordMetric("countArrayWrites");
    }
    std::vector<int> start(RADIX, 0);
    std::vector<int> end(RADIX, 0);
    std::vector<int> next(RADIX, 0);
    int sum = lo;
    for(int i=0; i<RADIX; i++) {
        start[i] = sum;
        next[i] = sum;
        sum += count[i];
        end[i] = sum;
    }
    for(int b=0; b<RADIX; b++) {
        int i = next[b];
        while((i < end[b])) {
            int d = digitFor(arr[i], currentDivisor);
            recordMetric("bucketScans");
            if((d == b)) {
                i++;
            } else {
                int to = next[d]++;
                swap(i, to);
                int t = arr[i];
                arr[i] = arr[to];
                arr[to] = t;
                recordMetric("cycleMoves");
            }
        }
    }
    if((currentDivisor == 1)) {
        for(int b=0; b<RADIX; b++) {
            if((count[b] > 0)) {
                for(int i=start[b]; i<end[b]; i++) {
                    markSorted(i);
                }
            }
        }
    } else {
        int nextDivisor = (currentDivisor / RADIX);
        for(int b=0; b<RADIX; b++) {
            if((count[b] > 1)) {
                recordMetric("recursiveBuckets");
                sortRange(start[b], end[b], nextDivisor);
            } else if((count[b] == 1)) {
                markSorted(start[b]);
            }
        }
    }
    checkpoint(((hi) < (n) ? (hi) : (n)), n);
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        return;
    }
    int metrics = educational.metrics;
    int min = arr[0];
    int max = arr[0];
    for(int i=1; i<n; i++) {
        if((arr[i] < min)) {
            min = arr[i];
        }
        if((arr[i] > max)) {
            max = arr[i];
        }
    }
    int RADIX = 256;
    int offset = (((min < 0)) ? (-min) : (0));
    int maxKey = (max + offset);
    metrics.radixBase = RADIX;
    metrics.signedOffset = offset;
    int divisor = 1;
    while(((maxKey / divisor) >= RADIX)) {
        divisor *= RADIX;
    }
    sortRange(0, n, divisor);
}

void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

int digitFor(int value, int currentDivisor) {
    recordMetric("digitExtractions");
    return (((value + offset) / currentDivisor) % RADIX);
}

void sortRange(int lo, int hi, int currentDivisor) {
    if((((hi - lo) <= 1) || (currentDivisor == 0))) {
        if(((hi - lo) == 1)) {
            markSorted(lo);
        }
        return;
    }
    recordMetric("distributionPasses");
    int[] count = new int[RADIX];
    for(int i=lo; i<hi; i++) {
        int d = digitFor(arr[i], currentDivisor);
        count[d]++;
        recordMetric("countArrayWrites");
    }
    int[] start = new int[RADIX];
    int[] end = new int[RADIX];
    int[] next = new int[RADIX];
    int sum = lo;
    for(int i=0; i<RADIX; i++) {
        start[i] = sum;
        next[i] = sum;
        sum += count[i];
        end[i] = sum;
    }
    for(int b=0; b<RADIX; b++) {
        int i = next[b];
        while((i < end[b])) {
            int d = digitFor(arr[i], currentDivisor);
            recordMetric("bucketScans");
            if((d == b)) {
                i++;
            } else {
                int to = next[d]++;
                swap(i, to);
                int t = arr[i];
                arr[i] = arr[to];
                arr[to] = t;
                recordMetric("cycleMoves");
            }
        }
    }
    if((currentDivisor == 1)) {
        for(int b=0; b<RADIX; b++) {
            if((count[b] > 0)) {
                for(int i=start[b]; i<end[b]; i++) {
                    markSorted(i);
                }
            }
        }
    } else {
        int nextDivisor = (currentDivisor / RADIX);
        for(int b=0; b<RADIX; b++) {
            if((count[b] > 1)) {
                recordMetric("recursiveBuckets");
                sortRange(start[b], end[b], nextDivisor);
            } else if((count[b] == 1)) {
                markSorted(start[b]);
            }
        }
    }
    checkpoint(Math.Min(hi, n), n);
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        return;
    }
    int metrics = stats.educational.metrics;
    int min = arr[0];
    int max = arr[0];
    for(int i=1; i<n; i++) {
        if((arr[i] < min)) {
            min = arr[i];
        }
        if((arr[i] > max)) {
            max = arr[i];
        }
    }
    int RADIX = 256;
    int offset = (((min < 0)) ? (-min) : (0));
    int maxKey = (max + offset);
    metrics.radixBase = RADIX;
    metrics.signedOffset = offset;
    int divisor = 1;
    while(((maxKey / divisor) >= RADIX)) {
        divisor *= RADIX;
    }
    sortRange(0, n, divisor);
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void recordMetric(int name, int );
int digitFor(int value, int currentDivisor);
void sortRange(int lo, int hi, int currentDivisor);

void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

int digitFor(int value, int currentDivisor) {
    recordMetric("digitExtractions");
    return (((value + offset) / currentDivisor) % RADIX);
}

void sortRange(int lo, int hi, int currentDivisor) {
    if((((hi - lo) <= 1) || (currentDivisor == 0))) {
        if(((hi - lo) == 1)) {
            markSorted(lo);
        }
        return;
    }
    recordMetric("distributionPasses");
    int* count = (int*)malloc((RADIX) * sizeof(int)); memset(count, 0, (RADIX) * sizeof(int));
    for(int i=lo; i<hi; i++) {
        int d = digitFor(arr[i], currentDivisor);
        count[d]++;
        recordMetric("countArrayWrites");
    }
    int* start = (int*)malloc((RADIX) * sizeof(int)); memset(start, 0, (RADIX) * sizeof(int));
    int* end = (int*)malloc((RADIX) * sizeof(int)); memset(end, 0, (RADIX) * sizeof(int));
    int* next = (int*)malloc((RADIX) * sizeof(int)); memset(next, 0, (RADIX) * sizeof(int));
    int sum = lo;
    for(int i=0; i<RADIX; i++) {
        start[i] = sum;
        next[i] = sum;
        sum += count[i];
        end[i] = sum;
    }
    for(int b=0; b<RADIX; b++) {
        int i = next[b];
        while((i < end[b])) {
            int d = digitFor(arr[i], currentDivisor);
            recordMetric("bucketScans");
            if((d == b)) {
                i++;
            } else {
                int to = next[d]++;
                swap(i, to);
                int t = arr[i];
                arr[i] = arr[to];
                arr[to] = t;
                recordMetric("cycleMoves");
            }
        }
    }
    if((currentDivisor == 1)) {
        for(int b=0; b<RADIX; b++) {
            if((count[b] > 0)) {
                for(int i=start[b]; i<end[b]; i++) {
                    markSorted(i);
                }
            }
        }
    } else {
        int nextDivisor = (currentDivisor / RADIX);
        for(int b=0; b<RADIX; b++) {
            if((count[b] > 1)) {
                recordMetric("recursiveBuckets");
                sortRange(start[b], end[b], nextDivisor);
            } else if((count[b] == 1)) {
                markSorted(start[b]);
            }
        }
    }
    checkpoint(((hi) < (n) ? (hi) : (n)), n);
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        return;
    }
    int metrics = (*educational).metrics;
    int min = arr[0];
    int max = arr[0];
    for(int i=1; i<n; i++) {
        if((arr[i] < min)) {
            min = arr[i];
        }
        if((arr[i] > max)) {
            max = arr[i];
        }
    }
    int RADIX = 256;
    int offset = (((min < 0)) ? (-min) : (0));
    int maxKey = (max + offset);
    metrics.radixBase = RADIX;
    metrics.signedOffset = offset;
    int divisor = 1;
    while(((maxKey / divisor) >= RADIX)) {
        divisor *= RADIX;
    }
    sortRange(0, n, divisor);
}