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 reverse(start, end) {
    while (start < end) {
      compare(start, end);
      let t = arr[start];
      arr[start] = arr[end];
      arr[end] = t;
      swap(start, end);
      start++;
      end--;
    }
  }
  function rotate(lo, mid, hi) {
    if (lo > mid || mid >= hi) return;
    reverse(lo, mid);
    reverse(mid + 1, hi);
    reverse(lo, hi);
  }
  function binarySearchLeft(start, end, target) {
    let lo = start, hi = end;
    while (lo <= hi) {
      let m = lo + Math.floor((hi - lo) / 2);
      compare(m, start);
      if (arr[m] < target) lo = m + 1; else hi = m - 1;
    }
    return lo;
  }
  function binarySearchRight(start, end, target) {
    let lo = start, hi = end;
    while (lo <= hi) {
      let m = lo + Math.floor((hi - lo) / 2);
      compare(m, start);
      if (arr[m] <= target) lo = m + 1; else hi = m - 1;
    }
    return lo;
  }
  function merge(lo, mid, hi) {
    if (lo > mid || mid >= hi) return;
    compare(mid, mid + 1);
    if (arr[mid] <= arr[mid + 1]) return;
    let len1 = mid - lo + 1;
    let len2 = hi - mid;
    let midL, midR;
    if (len1 >= len2) {
      midL = lo + Math.floor(len1 / 2);
      midR = binarySearchLeft(mid + 1, hi, arr[midL]);
    } else {
      midR = mid + 1 + Math.floor(len2 / 2);
      midL = binarySearchRight(lo, mid, arr[midR]);
    }
    const newMid = midL + (midR - 1 - mid) - 1;
    rotate(midL, mid, midR - 1);
    merge(lo, midL - 1, newMid);
    merge(newMid + 1, midR - 1, hi);
  }
  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);
    }
    checkpoint(Math.min(width << 1, n), n);
  }
}

def grailSort(arr, stats):
    def insertion(lo, hi):
        for i in range((lo + 1), (hi + 1)):
            key = arr[i]
            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 -= 1
            arr[(j + 1)] = key
            write((j + 1), key)

    def reverse(start, end):
        while (start < end):
            compare(start, end)
            t = arr[start]
            arr[start] = arr[end]
            arr[end] = t
            swap(start, end)
            start += 1
            end -= 1

    def rotate(lo, mid, hi):
        if ((lo > mid) or (mid >= hi)):
            return
        reverse(lo, mid)
        reverse((mid + 1), hi)
        reverse(lo, hi)

    def binarySearchLeft(start, end, target):
        lo = start
        hi = end
        while (lo <= hi):
            m = (lo + ((hi - lo) // 2))
            compare(m, start)
            if (arr[m] < target):
                lo = (m + 1)
            else:
                hi = (m - 1)
        return lo

    def binarySearchRight(start, end, target):
        lo = start
        hi = end
        while (lo <= hi):
            m = (lo + ((hi - lo) // 2))
            compare(m, start)
            if (arr[m] <= target):
                lo = (m + 1)
            else:
                hi = (m - 1)
        return lo

    def merge(lo, mid, hi):
        if ((lo > mid) or (mid >= hi)):
            return
        compare(mid, (mid + 1))
        if (arr[mid] <= arr[(mid + 1)]):
            return
        len1 = ((mid - lo) + 1)
        len2 = (hi - mid)
        midL = None
        midR = None
        if (len1 >= len2):
            midL = (lo + (len1 // 2))
            midR = binarySearchLeft((mid + 1), hi, arr[midL])
        else:
            midR = ((mid + 1) + (len2 // 2))
            midL = binarySearchRight(lo, mid, arr[midR])
        newMid = ((midL + ((midR - 1) - mid)) - 1)
        rotate(midL, mid, (midR - 1))
        merge(lo, (midL - 1), newMid)
        merge((newMid + 1), (midR - 1), hi)

    block = (4 if 4 >= int(int((n or 1) ** 0.5)) else int(int((n or 1) ** 0.5)))
    for i in range(0, n, block):
        insertion(i, (((i + block) - 1) if ((i + block) - 1) <= (n - 1) else (n - 1)))
    width = block
    while (width < n):
        for i in range(0, n, (width << 1)):
            lo = i
            mid = (((i + width) - 1) if ((i + width) - 1) <= (n - 1) else (n - 1))
            hi = (((i + (width << 1)) - 1) if ((i + (width << 1)) - 1) <= (n - 1) else (n - 1))
            if (mid < hi):
                merge(lo, mid, hi)
        checkpoint(((width << 1) if (width << 1) <= n else n), n)
        width <<= 1

#include <vector>
#include <algorithm>
#include <cmath>
void insertion(int lo, int hi);
void reverse(int start, int end);
void rotate(int lo, int mid, int hi);
int binarySearchLeft(int start, int end, int target);
int binarySearchRight(int start, int end, int target);
void merge(int lo, int mid, int hi);

void insertion(int lo, int hi) {
    for(int i=(lo + 1); i<(hi + 1); i++) {
        int key = arr[i];
        int 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);
    }
}

void reverse(int start, int end) {
    while((start < end)) {
        compare(start, end);
        int t = arr[start];
        arr[start] = arr[end];
        arr[end] = t;
        swap(start, end);
        start++;
        end--;
    }
}

void rotate(int lo, int mid, int hi) {
    if(((lo > mid) || (mid >= hi))) {
        return;
    }
    reverse(lo, mid);
    reverse((mid + 1), hi);
    reverse(lo, hi);
}

int binarySearchLeft(int start, int end, int target) {
    int lo = start;
    int hi = end;
    while((lo <= hi)) {
        int m = (lo + ((hi - lo) / 2));
        compare(m, start);
        if((arr[m] < target)) {
            lo = (m + 1);
        } else {
            hi = (m - 1);
        }
    }
    return lo;
}

int binarySearchRight(int start, int end, int target) {
    int lo = start;
    int hi = end;
    while((lo <= hi)) {
        int m = (lo + ((hi - lo) / 2));
        compare(m, start);
        if((arr[m] <= target)) {
            lo = (m + 1);
        } else {
            hi = (m - 1);
        }
    }
    return lo;
}

void merge(int lo, int mid, int hi) {
    if(((lo > mid) || (mid >= hi))) {
        return;
    }
    compare(mid, (mid + 1));
    if((arr[mid] <= arr[(mid + 1)])) {
        return;
    }
    int len1 = ((mid - lo) + 1);
    int len2 = (hi - mid);
    int midL;
    int midR;
    if((len1 >= len2)) {
        midL = (lo + (len1 / 2));
        midR = binarySearchLeft((mid + 1), hi, arr[midL]);
    } else {
        midR = ((mid + 1) + (len2 / 2));
        midL = binarySearchRight(lo, mid, arr[midR]);
    }
    int newMid = ((midL + ((midR - 1) - mid)) - 1);
    rotate(midL, mid, (midR - 1));
    merge(lo, (midL - 1), newMid);
    merge((newMid + 1), (midR - 1), hi);
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    int block = ((4) > ((int)std::floor((int)std::sqrt(((n) != 0 ? (n) : (1))))) ? (4) : ((int)std::floor((int)std::sqrt(((n) != 0 ? (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);
            }
        }
        checkpoint((((width << 1)) < (n) ? ((width << 1)) : (n)), n);
    }
}

void insertion(int lo, int hi) {
    for(int i=(lo + 1); i<(hi + 1); i++) {
        int key = arr[i];
        int 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);
    }
}

void reverse(int start, int end) {
    while((start < end)) {
        compare(start, end);
        int t = arr[start];
        arr[start] = arr[end];
        arr[end] = t;
        swap(start, end);
        start++;
        end--;
    }
}

void rotate(int lo, int mid, int hi) {
    if(((lo > mid) || (mid >= hi))) {
        return;
    }
    reverse(lo, mid);
    reverse((mid + 1), hi);
    reverse(lo, hi);
}

int binarySearchLeft(int start, int end, int target) {
    int lo = start;
    int hi = end;
    while((lo <= hi)) {
        int m = (lo + ((hi - lo) / 2));
        compare(m, start);
        if((arr[m] < target)) {
            lo = (m + 1);
        } else {
            hi = (m - 1);
        }
    }
    return lo;
}

int binarySearchRight(int start, int end, int target) {
    int lo = start;
    int hi = end;
    while((lo <= hi)) {
        int m = (lo + ((hi - lo) / 2));
        compare(m, start);
        if((arr[m] <= target)) {
            lo = (m + 1);
        } else {
            hi = (m - 1);
        }
    }
    return lo;
}

void merge(int lo, int mid, int hi) {
    if(((lo > mid) || (mid >= hi))) {
        return;
    }
    compare(mid, (mid + 1));
    if((arr[mid] <= arr[(mid + 1)])) {
        return;
    }
    int len1 = ((mid - lo) + 1);
    int len2 = (hi - mid);
    int midL;
    int midR;
    if((len1 >= len2)) {
        midL = (lo + (len1 / 2));
        midR = binarySearchLeft((mid + 1), hi, arr[midL]);
    } else {
        midR = ((mid + 1) + (len2 / 2));
        midL = binarySearchRight(lo, mid, arr[midR]);
    }
    int newMid = ((midL + ((midR - 1) - mid)) - 1);
    rotate(midL, mid, (midR - 1));
    merge(lo, (midL - 1), newMid);
    merge((newMid + 1), (midR - 1), hi);
}

public void Sort(int[] arr, int n, dynamic stats) {
    int block = Math.Max(4, (int)Math.Floor((double)(int)Math.Sqrt(((n) != 0 ? (n) : (1)))));
    for(int i=0; i<n; i+=block) {
        insertion(i, Math.Min(((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 = Math.Min(((i + width) - 1), (n - 1));
            int hi = Math.Min(((i + (width << 1)) - 1), (n - 1));
            if((mid < hi)) {
                merge(lo, mid, hi);
            }
        }
        checkpoint(Math.Min((width << 1), n), n);
    }
}

#include <stdio.h>
#include <math.h>
void insertion(int lo, int hi);
void reverse(int start, int end);
void rotate(int lo, int mid, int hi);
int binarySearchLeft(int start, int end, int target);
int binarySearchRight(int start, int end, int target);
void merge(int lo, int mid, int hi);

void insertion(int lo, int hi) {
    for(int i=(lo + 1); i<(hi + 1); i++) {
        int key = arr[i];
        int 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);
    }
}

void reverse(int start, int end) {
    while((start < end)) {
        compare(start, end);
        int t = arr[start];
        arr[start] = arr[end];
        arr[end] = t;
        swap(start, end);
        start++;
        end--;
    }
}

void rotate(int lo, int mid, int hi) {
    if(((lo > mid) || (mid >= hi))) {
        return;
    }
    reverse(lo, mid);
    reverse((mid + 1), hi);
    reverse(lo, hi);
}

int binarySearchLeft(int start, int end, int target) {
    int lo = start;
    int hi = end;
    while((lo <= hi)) {
        int m = (lo + ((hi - lo) / 2));
        compare(m, start);
        if((arr[m] < target)) {
            lo = (m + 1);
        } else {
            hi = (m - 1);
        }
    }
    return lo;
}

int binarySearchRight(int start, int end, int target) {
    int lo = start;
    int hi = end;
    while((lo <= hi)) {
        int m = (lo + ((hi - lo) / 2));
        compare(m, start);
        if((arr[m] <= target)) {
            lo = (m + 1);
        } else {
            hi = (m - 1);
        }
    }
    return lo;
}

void merge(int lo, int mid, int hi) {
    if(((lo > mid) || (mid >= hi))) {
        return;
    }
    compare(mid, (mid + 1));
    if((arr[mid] <= arr[(mid + 1)])) {
        return;
    }
    int len1 = ((mid - lo) + 1);
    int len2 = (hi - mid);
    int midL;
    int midR;
    if((len1 >= len2)) {
        midL = (lo + (len1 / 2));
        midR = binarySearchLeft((mid + 1), hi, arr[midL]);
    } else {
        midR = ((mid + 1) + (len2 / 2));
        midL = binarySearchRight(lo, mid, arr[midR]);
    }
    int newMid = ((midL + ((midR - 1) - mid)) - 1);
    rotate(midL, mid, (midR - 1));
    merge(lo, (midL - 1), newMid);
    merge((newMid + 1), (midR - 1), hi);
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    int block = ((4) > ((int)floor((int)sqrt(((n) != 0 ? (n) : (1))))) ? (4) : ((int)floor((int)sqrt(((n) != 0 ? (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);
            }
        }
        checkpoint((((width << 1)) < (n) ? ((width << 1)) : (n)), n);
    }
}