Grail Sort

function grailSort(arr, stats) {
  const n = arr.length;
  if (n < 2) return;
  const block = Math.max(4, Math.floor(Math.sqrt(n)));
  for (let lo = 0; lo < n; lo += block) {
    const hi = Math.min(lo + block, n);
    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;
    }
  }
  for (let width = block; width < n; width *= 2) {
    for (let lo = 0; lo < n; lo += 2 * width) {
      const mid = Math.min(lo + width, n);
      const hi = Math.min(lo + 2 * width, n);
      if (mid >= hi) continue;
      const left = arr.slice(lo, mid);
      let i = 0;
      let j = mid;
      let k = lo;
      while (i < left.length && j < hi) {
        if (left[i] <= arr[j]) {
          arr[k] = left[i];
          i++;
        } else {
          arr[k] = arr[j];
          j++;
        }
        k++;
      }
      while (i < left.length) {
        arr[k] = left[i];
        i++;
        k++;
      }
    }
  }
}

def sort(arr, n, stats):
    if (n < 2):
        return
    block = max(4, int(int(n ** 0.5)))
    for lo in range(0, n, block):
        hi = min((lo + block), n)
        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
    width = block
    while (width < n):
        for lo in range(0, n, (2 * width)):
            mid = min((lo + width), n)
            hi = min((lo + (2 * width)), n)
            if (mid >= hi):
                continue
            left = arr[lo:mid]
            i = 0
            j = mid
            k = lo
            while ((i < len(left)) and (j < hi)):
                if (left[i] <= arr[j]):
                    arr[k] = left[i]
                    i += 1
                else:
                    arr[k] = arr[j]
                    j += 1
                k += 1
            while (i < len(left)):
                arr[k] = left[i]
                i += 1
                k += 1
        width *= 2

#include <vector>
#include <algorithm>
#include <cmath>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        return;
    }
    int block = ((4) > ((int)std::floor((int)std::sqrt(n))) ? (4) : ((int)std::floor((int)std::sqrt(n))));
    for(int lo=0; lo<n; lo+=block) {
        int hi = (((lo + block)) < (n) ? ((lo + block)) : (n));
        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;
        }
    }
    for(int width=block; (width < n); width *= 2) {
        for(int lo=0; lo<n; lo+=(2 * width)) {
            int mid = (((lo + width)) < (n) ? ((lo + width)) : (n));
            int hi = (((lo + (2 * width))) < (n) ? ((lo + (2 * width))) : (n));
            if((mid >= hi)) {
                continue;
            }
            int _left_len = mid - (lo);
            std::vector<int> left(arr.begin() + (lo), arr.begin() + (mid));
            int i = 0;
            int j = mid;
            int k = lo;
            while(((i < _left_len) && (j < hi))) {
                if((left[i] <= arr[j])) {
                    arr[k] = left[i];
                    i++;
                } else {
                    arr[k] = arr[j];
                    j++;
                }
                k++;
            }
            while((i < _left_len)) {
                arr[k] = left[i];
                i++;
                k++;
            }
        }
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        return;
    }
    int block = Math.Max(4, (int)Math.Floor((double)(int)Math.Sqrt(n)));
    for(int lo=0; lo<n; lo+=block) {
        int hi = Math.Min((lo + block), n);
        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;
        }
    }
    for(int width=block; (width < n); width *= 2) {
        for(int lo=0; lo<n; lo+=(2 * width)) {
            int mid = Math.Min((lo + width), n);
            int hi = Math.Min((lo + (2 * width)), n);
            if((mid >= hi)) {
                continue;
            }
            int _left_len = mid - (lo);
            int[] left = new int[_left_len];
            Array.Copy(arr, lo, left, 0, _left_len);
            int i = 0;
            int j = mid;
            int k = lo;
            while(((i < _left_len) && (j < hi))) {
                if((left[i] <= arr[j])) {
                    arr[k] = left[i];
                    i++;
                } else {
                    arr[k] = arr[j];
                    j++;
                }
                k++;
            }
            while((i < _left_len)) {
                arr[k] = left[i];
                i++;
                k++;
            }
        }
    }
}

#include <stdio.h>
#include <math.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        return;
    }
    int block = ((4) > ((int)floor((int)sqrt(n))) ? (4) : ((int)floor((int)sqrt(n))));
    for(int lo=0; lo<n; lo+=block) {
        int hi = (((lo + block)) < (n) ? ((lo + block)) : (n));
        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;
        }
    }
    for(int width=block; (width < n); width *= 2) {
        for(int lo=0; lo<n; lo+=(2 * width)) {
            int mid = (((lo + width)) < (n) ? ((lo + width)) : (n));
            int hi = (((lo + (2 * width))) < (n) ? ((lo + (2 * width))) : (n));
            if((mid >= hi)) {
                continue;
            }
            int _left_len = mid - (lo);
            int left[_left_len];
            for(int _ci=0;_ci<_left_len;_ci++) left[_ci]=arr[(lo)+_ci];
            int i = 0;
            int j = mid;
            int k = lo;
            while(((i < _left_len) && (j < hi))) {
                if((left[i] <= arr[j])) {
                    arr[k] = left[i];
                    i++;
                } else {
                    arr[k] = arr[j];
                    j++;
                }
                k++;
            }
            while((i < _left_len)) {
                arr[k] = left[i];
                i++;
                k++;
            }
        }
    }
}