Binary MSD Radix Sort

function binaryMSDRadixSort(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 offset = min < 0 ? -min : 0;
  const maxKey = max + offset;
  metrics.radixBase = 2;
  metrics.signedOffset = offset;
  let divisor = 1;
  while (Math.floor(maxKey / divisor) >= 2) divisor *= 2;
  function digitFor(value, currentDivisor) {
    recordMetric('bitInspections');
    return Math.floor((value + offset) / currentDivisor) % 2;
  }
  function sort(lo, hi, currentDivisor) {
    if (lo > hi) return;
    if (lo === hi || currentDivisor === 0) {
      for (let i = lo; i <= hi; i++) markSorted(i);
      return;
    }
    recordMetric('bitPasses');
    let i = lo;
    let j = hi;
    while (i <= j) {
      while (i <= j) {
        if (digitFor(arr[i], currentDivisor) !== 0) break;
        i++;
      }
      while (i <= j) {
        if (digitFor(arr[j], currentDivisor) === 0) break;
        j--;
      }
      if (i < j) {
        swap(i, j);
        const t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
        recordMetric('partitionSwaps');
        i++;
        j--;
      }
    }
    const nextDivisor = Math.floor(currentDivisor / 2);
    sort(lo, j, nextDivisor);
    sort(i, hi, nextDivisor);
  }
  sort(0, arr.length - 1, divisor);
}

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

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

    def sort(lo, hi, currentDivisor):
        if (lo > hi):
            return
        if ((lo == hi) or (currentDivisor == 0)):
            for i in range(lo, (hi + 1)):
                markSorted(i)
            return
        recordMetric("bitPasses")
        i = lo
        j = hi
        while (i <= j):
            while (i <= j):
                if (digitFor(arr[i], currentDivisor) != 0):
                    break
                i += 1
            while (i <= j):
                if (digitFor(arr[j], currentDivisor) == 0):
                    break
                j -= 1
            if (i < j):
                swap(i, j)
                t = arr[i]
                arr[i] = arr[j]
                arr[j] = t
                recordMetric("partitionSwaps")
                i += 1
                j -= 1
        nextDivisor = (currentDivisor // 2)
        sort(lo, j, nextDivisor)
        sort(i, hi, nextDivisor)

    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]
    offset = (-min if (min < 0) else 0)
    maxKey = (max + offset)
    metrics.radixBase = 2
    metrics.signedOffset = offset
    divisor = 1
    while (int(maxKey / divisor) >= 2):
        divisor *= 2
    sort(0, (len(arr) - 1), divisor)

#include <vector>
#include <algorithm>
void recordMetric(int name, int );
int digitFor(int value, int currentDivisor);
void sort(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("bitInspections");
    return (((value + offset) / currentDivisor) % 2);
}

void sort(int lo, int hi, int currentDivisor) {
    if((lo > hi)) {
        return;
    }
    if(((lo == hi) || (currentDivisor == 0))) {
        for(int i=lo; i<(hi + 1); i++) {
            markSorted(i);
        }
        return;
    }
    recordMetric("bitPasses");
    int i = lo;
    int j = hi;
    while((i <= j)) {
        while((i <= j)) {
            if((digitFor(arr[i], currentDivisor) != 0)) {
                break;
            }
            i++;
        }
        while((i <= j)) {
            if((digitFor(arr[j], currentDivisor) == 0)) {
                break;
            }
            j--;
        }
        if((i < j)) {
            swap(i, j);
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
            recordMetric("partitionSwaps");
            i++;
            j--;
        }
    }
    int nextDivisor = (currentDivisor / 2);
    sort(lo, j, nextDivisor);
    sort(i, hi, nextDivisor);
}

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 offset = (((min < 0)) ? (-min) : (0));
    int maxKey = (max + offset);
    metrics.radixBase = 2;
    metrics.signedOffset = offset;
    int divisor = 1;
    while(((maxKey / divisor) >= 2)) {
        divisor *= 2;
    }
    sort(0, (n - 1), divisor);
}

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

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

void sort(int lo, int hi, int currentDivisor) {
    if((lo > hi)) {
        return;
    }
    if(((lo == hi) || (currentDivisor == 0))) {
        for(int i=lo; i<(hi + 1); i++) {
            markSorted(i);
        }
        return;
    }
    recordMetric("bitPasses");
    int i = lo;
    int j = hi;
    while((i <= j)) {
        while((i <= j)) {
            if((digitFor(arr[i], currentDivisor) != 0)) {
                break;
            }
            i++;
        }
        while((i <= j)) {
            if((digitFor(arr[j], currentDivisor) == 0)) {
                break;
            }
            j--;
        }
        if((i < j)) {
            swap(i, j);
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
            recordMetric("partitionSwaps");
            i++;
            j--;
        }
    }
    int nextDivisor = (currentDivisor / 2);
    sort(lo, j, nextDivisor);
    sort(i, hi, nextDivisor);
}

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 offset = (((min < 0)) ? (-min) : (0));
    int maxKey = (max + offset);
    metrics.radixBase = 2;
    metrics.signedOffset = offset;
    int divisor = 1;
    while(((maxKey / divisor) >= 2)) {
        divisor *= 2;
    }
    sort(0, (n - 1), divisor);
}

#include <stdio.h>
void recordMetric(int name, int );
int digitFor(int value, int currentDivisor);
void sort(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("bitInspections");
    return (((value + offset) / currentDivisor) % 2);
}

void sort(int lo, int hi, int currentDivisor) {
    if((lo > hi)) {
        return;
    }
    if(((lo == hi) || (currentDivisor == 0))) {
        for(int i=lo; i<(hi + 1); i++) {
            markSorted(i);
        }
        return;
    }
    recordMetric("bitPasses");
    int i = lo;
    int j = hi;
    while((i <= j)) {
        while((i <= j)) {
            if((digitFor(arr[i], currentDivisor) != 0)) {
                break;
            }
            i++;
        }
        while((i <= j)) {
            if((digitFor(arr[j], currentDivisor) == 0)) {
                break;
            }
            j--;
        }
        if((i < j)) {
            swap(i, j);
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
            recordMetric("partitionSwaps");
            i++;
            j--;
        }
    }
    int nextDivisor = (currentDivisor / 2);
    sort(lo, j, nextDivisor);
    sort(i, hi, nextDivisor);
}

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 offset = (((min < 0)) ? (-min) : (0));
    int maxKey = (max + offset);
    metrics.radixBase = 2;
    metrics.signedOffset = offset;
    int divisor = 1;
    while(((maxKey / divisor) >= 2)) {
        divisor *= 2;
    }
    sort(0, (n - 1), divisor);
}