Grail Sort

function grailSort(arr, stats) {
  const n = arr.length;
  const block = Math.max(4, 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);
    }
  }
  function merge(lo, mid, hi) {
    const left = arr.slice(lo, mid + 1);
    let i = 0;
    let j = mid + 1;
    let k = lo;
    while (i < left.length && j <= hi) {
      compare(lo + i, j);
      if (left[i] <= arr[j]) arr[k++] = left[i++]; else arr[k++] = arr[j++];
      write(k - 1, arr[k - 1]);
    }
    while (i < left.length) {
      arr[k++] = left[i++];
      write(k - 1, arr[k - 1]);
    }
  }
  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(4, 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
    def merge(lo, mid, hi):
        left = arr[lo:(mid + 1)]
        i = 0
        j = (mid + 1)
        k = lo
        while ((i < len(left)) and (j <= hi)):
            if (left[i] <= arr[j]):
                arr[k] = left[i]
                k += 1
                i += 1
            else:
                arr[k] = arr[j]
                k += 1
                j += 1
        while (i < len(left)):
            arr[k] = left[i]
            k += 1
            i += 1
    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 _left_len = (mid + 1) - (lo);
        std::vector<int> left(_left_len);
        for(int _ci=0;_ci<_left_len;_ci++) left[_ci]=arr[(lo)+_ci];
        int i = 0;
        int j = (mid + 1);
        int k = lo;
        while(((i < _left_len) && (j <= hi))) {
            if((left[i] <= arr[j])) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = arr[j++];
            }
        }
        while((i < _left_len)) {
            arr[k++] = left[i++];
        }
    }
    int block = ((4) > ((int)std::floor((int)std::sqrt((n || 1)))) ? (4) : ((int)std::floor((int)std::sqrt((n || 1)))));
    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 _left_len = (mid + 1) - (lo);
        int[] left = new int[_left_len];
        for(int _ci=0;_ci<_left_len;_ci++) left[_ci]=arr[(lo)+_ci];
        int i = 0;
        int j = (mid + 1);
        int k = lo;
        while(((i < _left_len) && (j <= hi))) {
            if((left[i] <= arr[j])) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = arr[j++];
            }
        }
        while((i < _left_len)) {
            arr[k++] = left[i++];
        }
    }
    int block = ((4) > ((int)Math.Floor((int)Math.Sqrt((n || 1)))) ? (4) : ((int)Math.Floor((int)Math.Sqrt((n || 1)))));
    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 _left_len = (mid + 1) - (lo);
        int left[_left_len];
        for(int _ci=0;_ci<_left_len;_ci++) left[_ci]=arr[(lo)+_ci];
        int i = 0;
        int j = (mid + 1);
        int k = lo;
        while(((i < _left_len) && (j <= hi))) {
            if((left[i] <= arr[j])) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = arr[j++];
            }
        }
        while((i < _left_len)) {
            arr[k++] = left[i++];
        }
    }
    int block = ((4) > ((int)floor((int)sqrt((n || 1)))) ? (4) : ((int)floor((int)sqrt((n || 1)))));
    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);
            }
        }
    }
}