Sqrt Sort

function sqrtSort(arr, stats) {
  const n = arr.length;
  const block = Math.max(2, Math.floor(Math.sqrt(n || 1)));
  function insertion(lo, hi) {
    for (let i = lo + 1; i <= hi; i++) {
      const key = arr[i];
      let j = i - 1;
      while (j >= lo) {
        compare(j, i);
        if (arr[j] <= key) break;
        arr[j + 1] = arr[j];
        write(j + 1, arr[j + 1]);
        j--;
      }
      arr[j + 1] = key;
      write(j + 1, key);
    }
  }
  const temp = new Array(n);
  function merge(lo, mid, hi) {
    let i = lo;
    let j = mid + 1;
    let k = lo;
    while (i <= mid && j <= hi) {
      compare(i, j);
      temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= hi) temp[k++] = arr[j++];
    for (let p = lo; p <= hi; p++) {
      arr[p] = temp[p];
      write(p, arr[p]);
    }
  }
  for (let i = 0; i < n; i += block) insertion(i, Math.min(i + block - 1, n - 1));
  for (let width = block; width < n; width <<= 1) {
    for (let i = 0; i < n; i += width << 1) {
      const lo = i;
      const mid = Math.min(i + width - 1, n - 1);
      const hi = Math.min(i + (width << 1) - 1, n - 1);
      if (mid < hi) merge(lo, mid, hi);
    }
  }
}

def sort(arr, n, stats):
    block = max(2, int(int((n or 1) ** 0.5)))
    def insertion(lo, hi):
        for i in range((lo + 1), hi + 1):
            key = arr[i]
            j = (i - 1)
            while (j >= lo):
                if (arr[j] <= key):
                    break
                arr[(j + 1)] = arr[j]
                j -= 1
            arr[(j + 1)] = key
    temp = [0] * n
    def merge(lo, mid, hi):
        i = lo
        j = (mid + 1)
        k = lo
        while ((i <= mid) and (j <= hi)):
            temp[k] = (arr[i] if (arr[i] <= arr[j]) else arr[j])
            k += 1
            i += 1
            j += 1
        while (i <= mid):
            temp[k] = arr[i]
            k += 1
            i += 1
        while (j <= hi):
            temp[k] = arr[j]
            k += 1
            j += 1
        for p in range(lo, hi + 1):
            arr[p] = temp[p]
    i = 0
    while (i < n):
        insertion(i, min(((i + block) - 1), (n - 1)))
        i += block
    width = block
    while (width < n):
        i = 0
        while (i < n):
            lo = i
            mid = min(((i + width) - 1), (n - 1))
            hi = min(((i + (width << 1)) - 1), (n - 1))
            if (mid < hi):
                merge(lo, mid, hi)
            i += (width << 1)
        width <<= 1

#include <vector>
#include <algorithm>
#include <cmath>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    void insertion(int lo, int hi) {
        for(int i=(lo + 1); (i <= hi); i++) {
            int key = arr[i];
            int j = (i - 1);
            while((j >= lo)) {
                if((arr[j] <= key)) {
                    break;
                }
                arr[(j + 1)] = arr[j];
                j--;
            }
            arr[(j + 1)] = key;
        }
    }
    void merge(int lo, int mid, int hi) {
        int i = lo;
        int j = (mid + 1);
        int k = lo;
        while(((i <= mid) && (j <= hi))) {
            temp[k++] = (((arr[i] <= arr[j])) ? (arr[i++]) : (arr[j++]));
        }
        while((i <= mid)) {
            temp[k++] = arr[i++];
        }
        while((j <= hi)) {
            temp[k++] = arr[j++];
        }
        for(int p=lo; (p <= hi); p++) {
            arr[p] = temp[p];
        }
    }
    int block = ((2) > ((int)std::floor((int)std::sqrt((n || 1)))) ? (2) : ((int)std::floor((int)std::sqrt((n || 1)))));
    std::vector<int> temp(n);
    for(int i=0; (i < n); i += block) {
        insertion(i, ((((i + block) - 1)) < ((n - 1)) ? (((i + block) - 1)) : ((n - 1))));
    }
    for(int width=block; (width < n); width <<= 1) {
        for(int i=0; (i < n); i += (width << 1)) {
            int lo = i;
            int mid = ((((i + width) - 1)) < ((n - 1)) ? (((i + width) - 1)) : ((n - 1)));
            int hi = ((((i + (width << 1)) - 1)) < ((n - 1)) ? (((i + (width << 1)) - 1)) : ((n - 1)));
            if((mid < hi)) {
                merge(lo, mid, hi);
            }
        }
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    void insertion(int lo, int hi) {
        for(int i=(lo + 1); (i <= hi); i++) {
            int key = arr[i];
            int j = (i - 1);
            while((j >= lo)) {
                if((arr[j] <= key)) {
                    break;
                }
                arr[(j + 1)] = arr[j];
                j--;
            }
            arr[(j + 1)] = key;
        }
    }
    void merge(int lo, int mid, int hi) {
        int i = lo;
        int j = (mid + 1);
        int k = lo;
        while(((i <= mid) && (j <= hi))) {
            temp[k++] = (((arr[i] <= arr[j])) ? (arr[i++]) : (arr[j++]));
        }
        while((i <= mid)) {
            temp[k++] = arr[i++];
        }
        while((j <= hi)) {
            temp[k++] = arr[j++];
        }
        for(int p=lo; (p <= hi); p++) {
            arr[p] = temp[p];
        }
    }
    int block = ((2) > ((int)Math.Floor((int)Math.Sqrt((n || 1)))) ? (2) : ((int)Math.Floor((int)Math.Sqrt((n || 1)))));
    int[] temp = new int[n];
    for(int i=0; (i < n); i += block) {
        insertion(i, ((((i + block) - 1)) < ((n - 1)) ? (((i + block) - 1)) : ((n - 1))));
    }
    for(int width=block; (width < n); width <<= 1) {
        for(int i=0; (i < n); i += (width << 1)) {
            int lo = i;
            int mid = ((((i + width) - 1)) < ((n - 1)) ? (((i + width) - 1)) : ((n - 1)));
            int hi = ((((i + (width << 1)) - 1)) < ((n - 1)) ? (((i + (width << 1)) - 1)) : ((n - 1)));
            if((mid < hi)) {
                merge(lo, mid, hi);
            }
        }
    }
}

#include <stdio.h>
#include <math.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    void insertion(int lo, int hi) {
        for(int i=(lo + 1); (i <= hi); i++) {
            int key = arr[i];
            int j = (i - 1);
            while((j >= lo)) {
                if((arr[j] <= key)) {
                    break;
                }
                arr[(j + 1)] = arr[j];
                j--;
            }
            arr[(j + 1)] = key;
        }
    }
    void merge(int lo, int mid, int hi) {
        int i = lo;
        int j = (mid + 1);
        int k = lo;
        while(((i <= mid) && (j <= hi))) {
            temp[k++] = (((arr[i] <= arr[j])) ? (arr[i++]) : (arr[j++]));
        }
        while((i <= mid)) {
            temp[k++] = arr[i++];
        }
        while((j <= hi)) {
            temp[k++] = arr[j++];
        }
        for(int p=lo; (p <= hi); p++) {
            arr[p] = temp[p];
        }
    }
    int block = ((2) > ((int)floor((int)sqrt((n || 1)))) ? (2) : ((int)floor((int)sqrt((n || 1)))));
    int temp[n];
    for(int i=0; (i < n); i += block) {
        insertion(i, ((((i + block) - 1)) < ((n - 1)) ? (((i + block) - 1)) : ((n - 1))));
    }
    for(int width=block; (width < n); width <<= 1) {
        for(int i=0; (i < n); i += (width << 1)) {
            int lo = i;
            int mid = ((((i + width) - 1)) < ((n - 1)) ? (((i + width) - 1)) : ((n - 1)));
            int hi = ((((i + (width << 1)) - 1)) < ((n - 1)) ? (((i + (width << 1)) - 1)) : ((n - 1)));
            if((mid < hi)) {
                merge(lo, mid, hi);
            }
        }
    }
}