Bottom-Up Merge Sort

function bottomUpMergeSort(arr, stats) {
  const n = arr.length;
  const tmp = new Array(n);
  for (let width = 1; width < n; width <<= 1) {
    for (let left = 0; left < n; left += width << 1) {
      const mid = Math.min(left + width, n);
      const right = Math.min(left + (width << 1), n);
      let i = left;
      let j = mid;
      let k = left;
      while (i < mid && j < right) {
        compare(i, j);
        if (arr[i] <= arr[j]) tmp[k++] = arr[i++]; else tmp[k++] = arr[j++];
      }
      while (i < mid) {
        tmp[k++] = arr[i++];
      }
      while (j < right) {
        tmp[k++] = arr[j++];
      }
      for (let p = left; p < right; p++) {
        arr[p] = tmp[p];
        write(p, arr[p]);
      }
    }
    checkpoint(Math.min(width << 1, n), n);
  }
}

def bottomUpMergeSort(arr, stats):
    tmp = [0] * n
    width = 1
    while (width < n):
        for left in range(0, n, (width << 1)):
            mid = ((left + width) if (left + width) <= n else n)
            right = ((left + (width << 1)) if (left + (width << 1)) <= n else n)
            i = left
            j = mid
            k = left
            while ((i < mid) and (j < right)):
                compare(i, j)
                if (arr[i] <= arr[j]):
                    tmp[((k := k + 1) - 1)] = arr[((i := i + 1) - 1)]
                else:
                    tmp[((k := k + 1) - 1)] = arr[((j := j + 1) - 1)]
            while (i < mid):
                tmp[((k := k + 1) - 1)] = arr[((i := i + 1) - 1)]
            while (j < right):
                tmp[((k := k + 1) - 1)] = arr[((j := j + 1) - 1)]
            for p in range(left, right):
                arr[p] = tmp[p]
                write(p, arr[p])
        checkpoint(((width << 1) if (width << 1) <= n else n), n)
        width <<= 1

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

public void Sort(int[] arr, int n, dynamic stats) {
    int[] tmp = new int[n];
    for(int width=1; (width < n); width <<= 1) {
        for(int left=0; left<n; left+=(width << 1)) {
            int mid = Math.Min((left + width), n);
            int right = Math.Min((left + (width << 1)), n);
            int i = left;
            int j = mid;
            int k = left;
            while(((i < mid) && (j < right))) {
                compare(i, j);
                if((arr[i] <= arr[j])) {
                    tmp[k++] = arr[i++];
                } else {
                    tmp[k++] = arr[j++];
                }
            }
            while((i < mid)) {
                tmp[k++] = arr[i++];
            }
            while((j < right)) {
                tmp[k++] = arr[j++];
            }
            for(int p=left; p<right; p++) {
                arr[p] = tmp[p];
                write(p, arr[p]);
            }
        }
        checkpoint(Math.Min((width << 1), n), n);
    }
}

#include <stdio.h>
#include <stdlib.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    int* tmp = (int*)malloc((n) * sizeof(int));
    for(int width=1; (width < n); width <<= 1) {
        for(int left=0; left<n; left+=(width << 1)) {
            int mid = (((left + width)) < (n) ? ((left + width)) : (n));
            int right = (((left + (width << 1))) < (n) ? ((left + (width << 1))) : (n));
            int i = left;
            int j = mid;
            int k = left;
            while(((i < mid) && (j < right))) {
                compare(i, j);
                if((arr[i] <= arr[j])) {
                    tmp[k++] = arr[i++];
                } else {
                    tmp[k++] = arr[j++];
                }
            }
            while((i < mid)) {
                tmp[k++] = arr[i++];
            }
            while((j < right)) {
                tmp[k++] = arr[j++];
            }
            for(int p=left; p<right; p++) {
                arr[p] = tmp[p];
                write(p, arr[p]);
            }
        }
        checkpoint((((width << 1)) < (n) ? ((width << 1)) : (n)), n);
    }
}