Shivers Sort

function shiversSort(arr, stats) {
  const n = arr.length;
  const runs = [];
  let i = 0;
  while (i < n) {
    let j = i + 1;
    while (j < n && arr[j - 1] <= arr[j]) {
      compare(j - 1, j);
      j++;
    }
    runs.push([i, j]);
    i = j;
  }
  const temp = new Array(n);
  function merge(a, b) {
    const lo = runs[a][0];
    const mid = runs[a][1];
    const hi = runs[b][1];
    let i1 = lo;
    let i2 = mid;
    let k = lo;
    while (i1 < mid && i2 < hi) {
      compare(i1, i2);
      if (arr[i1] <= arr[i2]) temp[k++] = arr[i1++]; else temp[k++] = arr[i2++];
    }
    while (i1 < mid) temp[k++] = arr[i1++];
    while (i2 < hi) temp[k++] = arr[i2++];
    for (let p = lo; p < hi; p++) {
      arr[p] = temp[p];
      write(p, arr[p]);
    }
    runs[a] = [lo, hi];
    runs.splice(b, 1);
  }
  while (runs.length > 1) {
    let merged = false;
    for (let r = 0; r + 2 < runs.length; r++) {
      const a = runs[r][1] - runs[r][0];
      const b = runs[r + 1][1] - runs[r + 1][0];
      const c = runs[r + 2][1] - runs[r + 2][0];
      if (a <= b + c) {
        merge(r, r + 1);
        merged = true;
        break;
      }
    }
    if (!merged) merge(runs.length - 2, runs.length - 1);
  }
}

def sort(arr, n, stats):
    runs = []
    i = 0
    while (i < n):
        j = (i + 1)
        while ((j < n) and (arr[(j - 1)] <= arr[j])):
            j += 1
        runs.append([i, j])
        i = j
    temp = [0] * n
    def merge(a, b):
        lo = runs[a][0]
        mid = runs[a][1]
        hi = runs[b][1]
        i1 = lo
        i2 = mid
        k = lo
        while ((i1 < mid) and (i2 < hi)):
            if (arr[i1] <= arr[i2]):
                temp[k] = arr[i1]
                k += 1
                i1 += 1
            else:
                temp[k] = arr[i2]
                k += 1
                i2 += 1
        while (i1 < mid):
            temp[k] = arr[i1]
            k += 1
            i1 += 1
        while (i2 < hi):
            temp[k] = arr[i2]
            k += 1
            i2 += 1
        for p in range(lo, hi):
            arr[p] = temp[p]
        runs[a] = [lo, hi]
        runs.pop(b)
    while (len(runs) > 1):
        merged = False
        for r in range(len(runs)):
            a = (runs[r][1] - runs[r][0])
            b = (runs[(r + 1)][1] - runs[(r + 1)][0])
            c = (runs[(r + 2)][1] - runs[(r + 2)][0])
            if (a <= (b + c)):
                merge(r, (r + 1))
                merged = True
                break
        if not merged:
            merge((len(runs) - 2), (len(runs) - 1))

#include <vector>
#include <algorithm>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    void merge(int a, int b) {
        int lo = runs[a][0];
        int mid = runs[a][1];
        int hi = runs[b][1];
        int i1 = lo;
        int i2 = mid;
        int k = lo;
        while(((i1 < mid) && (i2 < hi))) {
            if((arr[i1] <= arr[i2])) {
                temp[k++] = arr[i1++];
            } else {
                temp[k++] = arr[i2++];
            }
        }
        while((i1 < mid)) {
            temp[k++] = arr[i1++];
        }
        while((i2 < hi)) {
            temp[k++] = arr[i2++];
        }
        for(int p=lo; (p < hi); p++) {
            arr[p] = temp[p];
        }
        runs[a] = {lo, hi};
        runs_splice(b, 1);
    }
    int runs = {};
    int i = 0;
    while((i < n)) {
        int j = (i + 1);
        while(((j < n) && (arr[(j - 1)] <= arr[j]))) {
            j++;
        }
        runs[runs_len++] = {i, j};
        i = j;
    }
    std::vector<int> temp(n);
    while((n > 1)) {
        int merged = 0;
        for(int r=0; ((r + 2) < n); r++) {
            int a = (runs[r][1] - runs[r][0]);
            int b = (runs[(r + 1)][1] - runs[(r + 1)][0]);
            int c = (runs[(r + 2)][1] - runs[(r + 2)][0]);
            if((a <= (b + c))) {
                merge(r, (r + 1));
                merged = 1;
                break;
            }
        }
        if(!merged) {
            merge((n - 2), (n - 1));
        }
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    void merge(int a, int b) {
        int lo = runs[a][0];
        int mid = runs[a][1];
        int hi = runs[b][1];
        int i1 = lo;
        int i2 = mid;
        int k = lo;
        while(((i1 < mid) && (i2 < hi))) {
            if((arr[i1] <= arr[i2])) {
                temp[k++] = arr[i1++];
            } else {
                temp[k++] = arr[i2++];
            }
        }
        while((i1 < mid)) {
            temp[k++] = arr[i1++];
        }
        while((i2 < hi)) {
            temp[k++] = arr[i2++];
        }
        for(int p=lo; (p < hi); p++) {
            arr[p] = temp[p];
        }
        runs[a] = {lo, hi};
        runs_splice(b, 1);
    }
    int runs = {};
    int i = 0;
    while((i < n)) {
        int j = (i + 1);
        while(((j < n) && (arr[(j - 1)] <= arr[j]))) {
            j++;
        }
        runs[runs_len++] = {i, j};
        i = j;
    }
    int[] temp = new int[n];
    while((n > 1)) {
        int merged = 0;
        for(int r=0; ((r + 2) < n); r++) {
            int a = (runs[r][1] - runs[r][0]);
            int b = (runs[(r + 1)][1] - runs[(r + 1)][0]);
            int c = (runs[(r + 2)][1] - runs[(r + 2)][0]);
            if((a <= (b + c))) {
                merge(r, (r + 1));
                merged = 1;
                break;
            }
        }
        if(!merged) {
            merge((n - 2), (n - 1));
        }
    }
}

#include <stdio.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    void merge(int a, int b) {
        int lo = runs[a][0];
        int mid = runs[a][1];
        int hi = runs[b][1];
        int i1 = lo;
        int i2 = mid;
        int k = lo;
        while(((i1 < mid) && (i2 < hi))) {
            if((arr[i1] <= arr[i2])) {
                temp[k++] = arr[i1++];
            } else {
                temp[k++] = arr[i2++];
            }
        }
        while((i1 < mid)) {
            temp[k++] = arr[i1++];
        }
        while((i2 < hi)) {
            temp[k++] = arr[i2++];
        }
        for(int p=lo; (p < hi); p++) {
            arr[p] = temp[p];
        }
        runs[a] = {lo, hi};
        runs_splice(b, 1);
    }
    int runs = {};
    int i = 0;
    while((i < n)) {
        int j = (i + 1);
        while(((j < n) && (arr[(j - 1)] <= arr[j]))) {
            j++;
        }
        runs[runs_len++] = {i, j};
        i = j;
    }
    int temp[n];
    while((n > 1)) {
        int merged = 0;
        for(int r=0; ((r + 2) < n); r++) {
            int a = (runs[r][1] - runs[r][0]);
            int b = (runs[(r + 1)][1] - runs[(r + 1)][0]);
            int c = (runs[(r + 2)][1] - runs[(r + 2)][0]);
            if((a <= (b + c))) {
                merge(r, (r + 1));
                merged = 1;
                break;
            }
        }
        if(!merged) {
            merge((n - 2), (n - 1));
        }
    }
}