Binary Insertion Sort

function binaryInsertionSort(arr, stats) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    const key = arr[i];
    let left = 0;
    let right = i;
    while (left < right) {
      const mid = left + right >> 1;
      compare(mid, i);
      if (arr[mid] <= key) left = mid + 1; else right = mid;
    }
    for (let j = i; j > left; j--) {
      arr[j] = arr[j - 1];
      write(j, arr[j]);
    }
    arr[left] = key;
    write(left, key);
    checkpoint(i + 1, n);
  }
}

def binaryInsertionSort(arr, stats):
    for i in range(1, n):
        key = arr[i]
        left = 0
        right = i
        while (left < right):
            mid = ((left + right) >> 1)
            compare(mid, i)
            if (arr[mid] <= key):
                left = (mid + 1)
            else:
                right = mid
        for j in range(i, left, -1):
            arr[j] = arr[(j - 1)]
            write(j, arr[j])
        arr[left] = key
        write(left, key)
        checkpoint((i + 1), n)

#include <vector>
#include <algorithm>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    for(int i=1; i<n; i++) {
        int key = arr[i];
        int left = 0;
        int right = i;
        while((left < right)) {
            int mid = ((left + right) >> 1);
            compare(mid, i);
            if((arr[mid] <= key)) {
                left = (mid + 1);
            } else {
                right = mid;
            }
        }
        for(int j=i; j>left; j--) {
            arr[j] = arr[(j - 1)];
            write(j, arr[j]);
        }
        arr[left] = key;
        write(left, key);
        checkpoint((i + 1), n);
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    for(int i=1; i<n; i++) {
        int key = arr[i];
        int left = 0;
        int right = i;
        while((left < right)) {
            int mid = ((left + right) >> 1);
            compare(mid, i);
            if((arr[mid] <= key)) {
                left = (mid + 1);
            } else {
                right = mid;
            }
        }
        for(int j=i; j>left; j--) {
            arr[j] = arr[(j - 1)];
            write(j, arr[j]);
        }
        arr[left] = key;
        write(left, key);
        checkpoint((i + 1), n);
    }
}

#include <stdio.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    for(int i=1; i<n; i++) {
        int key = arr[i];
        int left = 0;
        int right = i;
        while((left < right)) {
            int mid = ((left + right) >> 1);
            compare(mid, i);
            if((arr[mid] <= key)) {
                left = (mid + 1);
            } else {
                right = mid;
            }
        }
        for(int j=i; j>left; j--) {
            arr[j] = arr[(j - 1)];
            write(j, arr[j]);
        }
        arr[left] = key;
        write(left, key);
        checkpoint((i + 1), n);
    }
}