Sample Sort

function sampleSort(arr, stats) {
  const n = arr.length;
  if (n < 2) return;
  const buckets = Math.max(2, Math.floor(Math.sqrt(n)));
  const splitters = new Array(buckets).fill(0);
  for (let s = 0; s < buckets - 1; s++) {
    const idx = Math.floor(((s + 1) * n) / buckets);
    splitters[s] = arr[idx];
  }
  for (let s = 1; s < buckets - 1; s++) {
    const key = splitters[s];
    let j = s - 1;
    while (j >= 0 && splitters[j] > key) {
      splitters[j + 1] = splitters[j];
      j--;
    }
    splitters[j + 1] = key;
  }
  const count = new Array(buckets).fill(0);
  const bucketOf = new Array(n).fill(0);
  for (let i = 0; i < n; i++) {
    let b = 0;
    while (b < buckets - 1 && arr[i] >= splitters[b]) {
      b++;
    }
    bucketOf[i] = b;
    count[b]++;
  }
  const offset = new Array(buckets).fill(0);
  let sum = 0;
  for (let b = 0; b < buckets; b++) {
    offset[b] = sum;
    sum = sum + count[b];
  }
  const temp = new Array(n).fill(0);
  const pos = new Array(buckets).fill(0);
  for (let b = 0; b < buckets; b++) {
    pos[b] = offset[b];
  }
  for (let i = 0; i < n; i++) {
    const b = bucketOf[i];
    temp[pos[b]] = arr[i];
    pos[b]++;
  }
  for (let i = 0; i < n; i++) {
    arr[i] = temp[i];
  }
  for (let b = 0; b < buckets; b++) {
    const lo = offset[b];
    const hi = offset[b] + count[b];
    for (let i = lo + 1; i < hi; i++) {
      const key = arr[i];
      let j = i - 1;
      while (j >= lo && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
      }
      arr[j + 1] = key;
    }
  }
}

def sort(arr, n, stats):
    if (n < 2):
        return
    buckets = max(2, int(int(n ** 0.5)))
    splitters = [0] * buckets
    for s in range((buckets - 1)):
        idx = (((s + 1) * n) // buckets)
        splitters[s] = arr[idx]
    for s in range(1, (buckets - 1)):
        key = splitters[s]
        j = (s - 1)
        while ((j >= 0) and (splitters[j] > key)):
            splitters[(j + 1)] = splitters[j]
            j -= 1
        splitters[(j + 1)] = key
    count = [0] * buckets
    bucketOf = [0] * n
    for i in range(n):
        b = 0
        while ((b < (buckets - 1)) and (arr[i] >= splitters[b])):
            b += 1
        bucketOf[i] = b
        count[b] += 1
    offset = [0] * buckets
    sum = 0
    for b in range(buckets):
        offset[b] = sum
        sum = (sum + count[b])
    temp = [0] * n
    pos = [0] * buckets
    for b in range(buckets):
        pos[b] = offset[b]
    for i in range(n):
        b = bucketOf[i]
        temp[pos[b]] = arr[i]
        pos[b] += 1
    for i in range(n):
        arr[i] = temp[i]
    for b in range(buckets):
        lo = offset[b]
        hi = (offset[b] + count[b])
        for i in range((lo + 1), hi):
            key = arr[i]
            j = (i - 1)
            while ((j >= lo) and (arr[j] > key)):
                arr[(j + 1)] = arr[j]
                j -= 1
            arr[(j + 1)] = key

#include <vector>
#include <algorithm>
#include <cmath>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        return;
    }
    int buckets = ((2) > ((int)std::floor((int)std::sqrt(n))) ? (2) : ((int)std::floor((int)std::sqrt(n))));
    std::vector<int> splitters(buckets, 0);
    for(int s=0; s<(buckets - 1); s++) {
        int idx = (((s + 1) * n) / buckets);
        splitters[s] = arr[idx];
    }
    for(int s=1; s<(buckets - 1); s++) {
        int key = splitters[s];
        int j = (s - 1);
        while(((j >= 0) && (splitters[j] > key))) {
            splitters[(j + 1)] = splitters[j];
            j--;
        }
        splitters[(j + 1)] = key;
    }
    std::vector<int> count(buckets, 0);
    std::vector<int> bucketOf(n, 0);
    for(int i=0; i<n; i++) {
        int b = 0;
        while(((b < (buckets - 1)) && (arr[i] >= splitters[b]))) {
            b++;
        }
        bucketOf[i] = b;
        count[b]++;
    }
    std::vector<int> offset(buckets, 0);
    int sum = 0;
    for(int b=0; b<buckets; b++) {
        offset[b] = sum;
        sum = (sum + count[b]);
    }
    std::vector<int> temp(n, 0);
    std::vector<int> pos(buckets, 0);
    for(int b=0; b<buckets; b++) {
        pos[b] = offset[b];
    }
    for(int i=0; i<n; i++) {
        int b = bucketOf[i];
        temp[pos[b]] = arr[i];
        pos[b]++;
    }
    for(int i=0; i<n; i++) {
        arr[i] = temp[i];
    }
    for(int b=0; b<buckets; b++) {
        int lo = offset[b];
        int hi = (offset[b] + count[b]);
        for(int i=(lo + 1); i<hi; i++) {
            int key = arr[i];
            int j = (i - 1);
            while(((j >= lo) && (arr[j] > key))) {
                arr[(j + 1)] = arr[j];
                j--;
            }
            arr[(j + 1)] = key;
        }
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        return;
    }
    int buckets = Math.Max(2, (int)Math.Floor((double)(int)Math.Sqrt(n)));
    int[] splitters = new int[buckets];
    for(int s=0; s<(buckets - 1); s++) {
        int idx = (((s + 1) * n) / buckets);
        splitters[s] = arr[idx];
    }
    for(int s=1; s<(buckets - 1); s++) {
        int key = splitters[s];
        int j = (s - 1);
        while(((j >= 0) && (splitters[j] > key))) {
            splitters[(j + 1)] = splitters[j];
            j--;
        }
        splitters[(j + 1)] = key;
    }
    int[] count = new int[buckets];
    int[] bucketOf = new int[n];
    for(int i=0; i<n; i++) {
        int b = 0;
        while(((b < (buckets - 1)) && (arr[i] >= splitters[b]))) {
            b++;
        }
        bucketOf[i] = b;
        count[b]++;
    }
    int[] offset = new int[buckets];
    int sum = 0;
    for(int b=0; b<buckets; b++) {
        offset[b] = sum;
        sum = (sum + count[b]);
    }
    int[] temp = new int[n];
    int[] pos = new int[buckets];
    for(int b=0; b<buckets; b++) {
        pos[b] = offset[b];
    }
    for(int i=0; i<n; i++) {
        int b = bucketOf[i];
        temp[pos[b]] = arr[i];
        pos[b]++;
    }
    for(int i=0; i<n; i++) {
        arr[i] = temp[i];
    }
    for(int b=0; b<buckets; b++) {
        int lo = offset[b];
        int hi = (offset[b] + count[b]);
        for(int i=(lo + 1); i<hi; i++) {
            int key = arr[i];
            int j = (i - 1);
            while(((j >= lo) && (arr[j] > key))) {
                arr[(j + 1)] = arr[j];
                j--;
            }
            arr[(j + 1)] = key;
        }
    }
}

#include <stdio.h>
#include <string.h>
#include <math.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        return;
    }
    int buckets = ((2) > ((int)floor((int)sqrt(n))) ? (2) : ((int)floor((int)sqrt(n))));
    int splitters[buckets]; memset(splitters, 0, sizeof(splitters));
    for(int s=0; s<(buckets - 1); s++) {
        int idx = (((s + 1) * n) / buckets);
        splitters[s] = arr[idx];
    }
    for(int s=1; s<(buckets - 1); s++) {
        int key = splitters[s];
        int j = (s - 1);
        while(((j >= 0) && (splitters[j] > key))) {
            splitters[(j + 1)] = splitters[j];
            j--;
        }
        splitters[(j + 1)] = key;
    }
    int count[buckets]; memset(count, 0, sizeof(count));
    int bucketOf[n]; memset(bucketOf, 0, sizeof(bucketOf));
    for(int i=0; i<n; i++) {
        int b = 0;
        while(((b < (buckets - 1)) && (arr[i] >= splitters[b]))) {
            b++;
        }
        bucketOf[i] = b;
        count[b]++;
    }
    int offset[buckets]; memset(offset, 0, sizeof(offset));
    int sum = 0;
    for(int b=0; b<buckets; b++) {
        offset[b] = sum;
        sum = (sum + count[b]);
    }
    int temp[n]; memset(temp, 0, sizeof(temp));
    int pos[buckets]; memset(pos, 0, sizeof(pos));
    for(int b=0; b<buckets; b++) {
        pos[b] = offset[b];
    }
    for(int i=0; i<n; i++) {
        int b = bucketOf[i];
        temp[pos[b]] = arr[i];
        pos[b]++;
    }
    for(int i=0; i<n; i++) {
        arr[i] = temp[i];
    }
    for(int b=0; b<buckets; b++) {
        int lo = offset[b];
        int hi = (offset[b] + count[b]);
        for(int i=(lo + 1); i<hi; i++) {
            int key = arr[i];
            int j = (i - 1);
            while(((j >= lo) && (arr[j] > key))) {
                arr[(j + 1)] = arr[j];
                j--;
            }
            arr[(j + 1)] = key;
        }
    }
}