Natural Merge Sort

function naturalMergeSort(arr, stats) {
  const n = arr.length;
  const temp = new Array(n);
  function merge(lo, mid, hi) {
    let i = lo;
    let j = mid;
    let k = lo;
    while (i < mid && j < hi) {
      compare(i, j);
      if (arr[i] <= arr[j]) temp[k++] = arr[i++]; else temp[k++] = arr[j++];
    }
    while (i < mid) {
      temp[k++] = arr[i++];
    }
    while (j < hi) {
      temp[k++] = arr[j++];
    }
    for (let p = lo; p < hi; p++) {
      arr[p] = temp[p];
      write(p, arr[p]);
    }
  }
  if (n < 2) return;
  let changed = true;
  while (changed) {
    changed = false;
    let start = 0;
    while (start < n) {
      let mid = start + 1;
      while (mid < n && arr[mid - 1] <= arr[mid]) {
        compare(mid - 1, mid);
        mid++;
      }
      if (mid >= n) break;
      let end = mid + 1;
      while (end < n && arr[end - 1] <= arr[end]) {
        compare(end - 1, end);
        end++;
      }
      merge(start, mid, end);
      changed = true;
      start = end;
    }
    checkpoint(changed ? 1 : n, n);
  }
}

def naturalMergeSort(arr, stats):
    def merge(lo, mid, hi):
        i = lo
        j = mid
        k = lo
        while ((i < mid) and (j < hi)):
            compare(i, j)
            if (arr[i] <= arr[j]):
                temp[((k := k + 1) - 1)] = arr[((i := i + 1) - 1)]
            else:
                temp[((k := k + 1) - 1)] = arr[((j := j + 1) - 1)]
        while (i < mid):
            temp[((k := k + 1) - 1)] = arr[((i := i + 1) - 1)]
        while (j < hi):
            temp[((k := k + 1) - 1)] = arr[((j := j + 1) - 1)]
        for p in range(lo, hi):
            arr[p] = temp[p]
            write(p, arr[p])

    temp = [0] * n
    if (n < 2):
        return
    changed = True
    while changed:
        changed = False
        start = 0
        while (start < n):
            mid = (start + 1)
            while ((mid < n) and (arr[(mid - 1)] <= arr[mid])):
                compare((mid - 1), mid)
                mid += 1
            if (mid >= n):
                break
            end = (mid + 1)
            while ((end < n) and (arr[(end - 1)] <= arr[end])):
                compare((end - 1), end)
                end += 1
            merge(start, mid, end)
            changed = True
            start = end
        checkpoint((1 if changed else n), n)

#include <vector>
#include <algorithm>
void merge(int lo, int mid, int hi);

void merge(int lo, int mid, int hi) {
    int i = lo;
    int j = mid;
    int k = lo;
    while(((i < mid) && (j < hi))) {
        compare(i, j);
        if((arr[i] <= arr[j])) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while((i < mid)) {
        temp[k++] = arr[i++];
    }
    while((j < hi)) {
        temp[k++] = arr[j++];
    }
    for(int p=lo; p<hi; p++) {
        arr[p] = temp[p];
        write(p, arr[p]);
    }
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    std::vector<int> temp(n, 0);
    if((n < 2)) {
        return;
    }
    int changed = 1;
    while(changed) {
        changed = 0;
        int start = 0;
        while((start < n)) {
            int mid = (start + 1);
            while(((mid < n) && (arr[(mid - 1)] <= arr[mid]))) {
                compare((mid - 1), mid);
                mid++;
            }
            if((mid >= n)) {
                break;
            }
            int end = (mid + 1);
            while(((end < n) && (arr[(end - 1)] <= arr[end]))) {
                compare((end - 1), end);
                end++;
            }
            merge(start, mid, end);
            changed = 1;
            start = end;
        }
        checkpoint(((changed) ? (1) : (n)), n);
    }
}

void merge(int lo, int mid, int hi) {
    int i = lo;
    int j = mid;
    int k = lo;
    while(((i < mid) && (j < hi))) {
        compare(i, j);
        if((arr[i] <= arr[j])) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while((i < mid)) {
        temp[k++] = arr[i++];
    }
    while((j < hi)) {
        temp[k++] = arr[j++];
    }
    for(int p=lo; p<hi; p++) {
        arr[p] = temp[p];
        write(p, arr[p]);
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    int[] temp = new int[n];
    if((n < 2)) {
        return;
    }
    int changed = true;
    while(changed) {
        changed = false;
        int start = 0;
        while((start < n)) {
            int mid = (start + 1);
            while(((mid < n) && (arr[(mid - 1)] <= arr[mid]))) {
                compare((mid - 1), mid);
                mid++;
            }
            if((mid >= n)) {
                break;
            }
            int end = (mid + 1);
            while(((end < n) && (arr[(end - 1)] <= arr[end]))) {
                compare((end - 1), end);
                end++;
            }
            merge(start, mid, end);
            changed = true;
            start = end;
        }
        checkpoint(((changed) ? (1) : (n)), n);
    }
}

#include <stdio.h>
#include <stdlib.h>
void merge(int lo, int mid, int hi);

void merge(int lo, int mid, int hi) {
    int i = lo;
    int j = mid;
    int k = lo;
    while(((i < mid) && (j < hi))) {
        compare(i, j);
        if((arr[i] <= arr[j])) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while((i < mid)) {
        temp[k++] = arr[i++];
    }
    while((j < hi)) {
        temp[k++] = arr[j++];
    }
    for(int p=lo; p<hi; p++) {
        arr[p] = temp[p];
        write(p, arr[p]);
    }
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    int* temp = (int*)malloc((n) * sizeof(int));
    if((n < 2)) {
        return;
    }
    int changed = 1;
    while(changed) {
        changed = 0;
        int start = 0;
        while((start < n)) {
            int mid = (start + 1);
            while(((mid < n) && (arr[(mid - 1)] <= arr[mid]))) {
                compare((mid - 1), mid);
                mid++;
            }
            if((mid >= n)) {
                break;
            }
            int end = (mid + 1);
            while(((end < n) && (arr[(end - 1)] <= arr[end]))) {
                compare((end - 1), end);
                end++;
            }
            merge(start, mid, end);
            changed = 1;
            start = end;
        }
        checkpoint(((changed) ? (1) : (n)), n);
    }
}