In-Place Merge Sort

function inPlaceMergeSort(arr, stats) {
  const n = arr.length;
  function nextGap(gap) {
    if (gap <= 1) return 0;
    return (gap >> 1) + (gap & 1);
  }
  function mergeInPlace(left, mid, right) {
    for (let gap = nextGap(right - left + 1); gap > 0; gap = nextGap(gap)) {
      for (let i = left; i + gap <= right; i++) {
        const j = i + gap;
        compare(i, j);
        if (arr[i] > arr[j]) {
          swap(i, j);
          const t = arr[i];
          arr[i] = arr[j];
          arr[j] = t;
        }
      }
    }
  }
  function sort(lo, hi) {
    if (lo >= hi) return;
    const mid = lo + hi >> 1;
    sort(lo, mid);
    sort(mid + 1, hi);
    mergeInPlace(lo, mid, hi);
  }
  sort(0, n - 1);
}

def sort(arr, n, stats):
    def nextGap(gap):
        if (gap <= 1):
            return 0
        return ((gap >> 1) + (gap & 1))
    def mergeInPlace(left, mid, right):
        gap = nextGap(((right - left) + 1))
        while (gap > 0):
            for i in range(left, right + 1):
                j = (i + gap)
                if (arr[i] > arr[j]):
                    t = arr[i]
                    arr[i] = arr[j]
                    arr[j] = t
            gap = nextGap(gap)
    def sort(lo, hi):
        if (lo >= hi):
            return
        mid = ((lo + hi) >> 1)
        sort(lo, mid)
        sort((mid + 1), hi)
        mergeInPlace(lo, mid, hi)
    sort(0, (n - 1))

#include <vector>
#include <algorithm>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    int nextGap(int gap) {
        if((gap <= 1)) {
            return 0;
        }
        return ((gap >> 1) + (gap & 1));
    }
    void mergeInPlace(int left, int mid, int right) {
        for(int gap=nextGap(((right - left) + 1)); (gap > 0); gap = nextGap(gap)) {
            for(int i=left; ((i + gap) <= right); i++) {
                int j = (i + gap);
                if((arr[i] > arr[j])) {
                    int t = arr[i];
                    arr[i] = arr[j];
                    arr[j] = t;
                }
            }
        }
    }
    void sort(int lo, int hi) {
        if((lo >= hi)) {
            return;
        }
        int mid = ((lo + hi) >> 1);
        sort(lo, mid);
        sort((mid + 1), hi);
        mergeInPlace(lo, mid, hi);
    }
    sort(0, (n - 1));
}

public void Sort(int[] arr, int n, dynamic stats) {
    int nextGap(int gap) {
        if((gap <= 1)) {
            return 0;
        }
        return ((gap >> 1) + (gap & 1));
    }
    void mergeInPlace(int left, int mid, int right) {
        for(int gap=nextGap(((right - left) + 1)); (gap > 0); gap = nextGap(gap)) {
            for(int i=left; ((i + gap) <= right); i++) {
                int j = (i + gap);
                if((arr[i] > arr[j])) {
                    int t = arr[i];
                    arr[i] = arr[j];
                    arr[j] = t;
                }
            }
        }
    }
    void sort(int lo, int hi) {
        if((lo >= hi)) {
            return;
        }
        int mid = ((lo + hi) >> 1);
        sort(lo, mid);
        sort((mid + 1), hi);
        mergeInPlace(lo, mid, hi);
    }
    sort(0, (n - 1));
}

#include <stdio.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    int nextGap(int gap) {
        if((gap <= 1)) {
            return 0;
        }
        return ((gap >> 1) + (gap & 1));
    }
    void mergeInPlace(int left, int mid, int right) {
        for(int gap=nextGap(((right - left) + 1)); (gap > 0); gap = nextGap(gap)) {
            for(int i=left; ((i + gap) <= right); i++) {
                int j = (i + gap);
                if((arr[i] > arr[j])) {
                    int t = arr[i];
                    arr[i] = arr[j];
                    arr[j] = t;
                }
            }
        }
    }
    void sort(int lo, int hi) {
        if((lo >= hi)) {
            return;
        }
        int mid = ((lo + hi) >> 1);
        sort(lo, mid);
        sort((mid + 1), hi);
        mergeInPlace(lo, mid, hi);
    }
    sort(0, (n - 1));
}