External Merge Sort

function externalMergeSort(arr, stats) {
  const n = arr.length;
  const runSize = 32;
  for (let start = 0; start < n; start += runSize) {
    const end = Math.min(start + runSize, n);
    for (let i = start + 1; i < end; i++) {
      const key = arr[i];
      let j = i - 1;
      while (j >= start && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
      }
      arr[j + 1] = key;
    }
  }
  const buffer = new Array(n).fill(0);
  for (let width = runSize; width < n; width *= 2) {
    for (let left = 0; left < n; left += 2 * width) {
      const mid = Math.min(left + width, n);
      const right = Math.min(left + 2 * width, n);
      let i = left;
      let j = mid;
      let k = left;
      while (i < mid && j < right) {
        if (arr[i] <= arr[j]) {
          buffer[k] = arr[i];
          i++;
        } else {
          buffer[k] = arr[j];
          j++;
        }
        k++;
      }
      while (i < mid) {
        buffer[k] = arr[i];
        i++;
        k++;
      }
      while (j < right) {
        buffer[k] = arr[j];
        j++;
        k++;
      }
      for (let t = left; t < right; t++) arr[t] = buffer[t];
    }
  }
}

def sort(arr, n, stats):
    runSize = 32
    for start in range(0, n, runSize):
        end = min((start + runSize), n)
        for i in range((start + 1), end):
            key = arr[i]
            j = (i - 1)
            while ((j >= start) and (arr[j] > key)):
                arr[(j + 1)] = arr[j]
                j -= 1
            arr[(j + 1)] = key
    buffer = [0] * n
    width = runSize
    while (width < n):
        for left in range(0, n, (2 * width)):
            mid = min((left + width), n)
            right = min((left + (2 * width)), n)
            i = left
            j = mid
            k = left
            while ((i < mid) and (j < right)):
                if (arr[i] <= arr[j]):
                    buffer[k] = arr[i]
                    i += 1
                else:
                    buffer[k] = arr[j]
                    j += 1
                k += 1
            while (i < mid):
                buffer[k] = arr[i]
                i += 1
                k += 1
            while (j < right):
                buffer[k] = arr[j]
                j += 1
                k += 1
            for t in range(left, right):
                arr[t] = buffer[t]
        width *= 2

#include <vector>
#include <algorithm>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    int runSize = 32;
    for(int start=0; start<n; start+=runSize) {
        int end = (((start + runSize)) < (n) ? ((start + runSize)) : (n));
        for(int i=(start + 1); i<end; i++) {
            int key = arr[i];
            int j = (i - 1);
            while(((j >= start) && (arr[j] > key))) {
                arr[(j + 1)] = arr[j];
                j--;
            }
            arr[(j + 1)] = key;
        }
    }
    std::vector<int> buffer(n, 0);
    for(int width=runSize; (width < n); width *= 2) {
        for(int left=0; left<n; left+=(2 * width)) {
            int mid = (((left + width)) < (n) ? ((left + width)) : (n));
            int right = (((left + (2 * width))) < (n) ? ((left + (2 * width))) : (n));
            int i = left;
            int j = mid;
            int k = left;
            while(((i < mid) && (j < right))) {
                if((arr[i] <= arr[j])) {
                    buffer[k] = arr[i];
                    i++;
                } else {
                    buffer[k] = arr[j];
                    j++;
                }
                k++;
            }
            while((i < mid)) {
                buffer[k] = arr[i];
                i++;
                k++;
            }
            while((j < right)) {
                buffer[k] = arr[j];
                j++;
                k++;
            }
            for(int t=left; t<right; t++) {
                arr[t] = buffer[t];
            }
        }
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    int runSize = 32;
    for(int start=0; start<n; start+=runSize) {
        int end = Math.Min((start + runSize), n);
        for(int i=(start + 1); i<end; i++) {
            int key = arr[i];
            int j = (i - 1);
            while(((j >= start) && (arr[j] > key))) {
                arr[(j + 1)] = arr[j];
                j--;
            }
            arr[(j + 1)] = key;
        }
    }
    int[] buffer = new int[n];
    for(int width=runSize; (width < n); width *= 2) {
        for(int left=0; left<n; left+=(2 * width)) {
            int mid = Math.Min((left + width), n);
            int right = Math.Min((left + (2 * width)), n);
            int i = left;
            int j = mid;
            int k = left;
            while(((i < mid) && (j < right))) {
                if((arr[i] <= arr[j])) {
                    buffer[k] = arr[i];
                    i++;
                } else {
                    buffer[k] = arr[j];
                    j++;
                }
                k++;
            }
            while((i < mid)) {
                buffer[k] = arr[i];
                i++;
                k++;
            }
            while((j < right)) {
                buffer[k] = arr[j];
                j++;
                k++;
            }
            for(int t=left; t<right; t++) {
                arr[t] = buffer[t];
            }
        }
    }
}

#include <stdio.h>
#include <string.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    int runSize = 32;
    for(int start=0; start<n; start+=runSize) {
        int end = (((start + runSize)) < (n) ? ((start + runSize)) : (n));
        for(int i=(start + 1); i<end; i++) {
            int key = arr[i];
            int j = (i - 1);
            while(((j >= start) && (arr[j] > key))) {
                arr[(j + 1)] = arr[j];
                j--;
            }
            arr[(j + 1)] = key;
        }
    }
    int buffer[n]; memset(buffer, 0, sizeof(buffer));
    for(int width=runSize; (width < n); width *= 2) {
        for(int left=0; left<n; left+=(2 * width)) {
            int mid = (((left + width)) < (n) ? ((left + width)) : (n));
            int right = (((left + (2 * width))) < (n) ? ((left + (2 * width))) : (n));
            int i = left;
            int j = mid;
            int k = left;
            while(((i < mid) && (j < right))) {
                if((arr[i] <= arr[j])) {
                    buffer[k] = arr[i];
                    i++;
                } else {
                    buffer[k] = arr[j];
                    j++;
                }
                k++;
            }
            while((i < mid)) {
                buffer[k] = arr[i];
                i++;
                k++;
            }
            while((j < right)) {
                buffer[k] = arr[j];
                j++;
                k++;
            }
            for(int t=left; t<right; t++) {
                arr[t] = buffer[t];
            }
        }
    }
}