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 shiversSort(arr, stats):
    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)):
            compare(i1, i2)
            if (arr[i1] <= arr[i2]):
                temp[((k := k + 1) - 1)] = arr[((i1 := i1 + 1) - 1)]
            else:
                temp[((k := k + 1) - 1)] = arr[((i2 := i2 + 1) - 1)]
        while (i1 < mid):
            temp[((k := k + 1) - 1)] = arr[((i1 := i1 + 1) - 1)]
        while (i2 < hi):
            temp[((k := k + 1) - 1)] = arr[((i2 := i2 + 1) - 1)]
        for p in range(lo, hi):
            arr[p] = temp[p]
            write(p, arr[p])
        runs[a] = [lo, hi]
        runs.pop(b)

    runs = []
    i = 0
    while (i < n):
        j = (i + 1)
        while ((j < n) and (arr[(j - 1)] <= arr[j])):
            compare((j - 1), j)
            j += 1
        runs.append([i, j])
        i = j
    temp = [0] * n
    while (len(runs) > 1):
        merged = False
        r = 0
        while ((r + 2) < 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
            r += 1
        if not merged:
            merge((len(runs) - 2), (len(runs) - 1))

#include <vector>
#include <algorithm>
void merge(int a, int b);

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))) {
        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(int p=lo; p<hi; p++) {
        arr[p] = temp[p];
        write(p, arr[p]);
    }
    runs[a] = {lo, hi};
    runs.erase(runs.begin() + b);
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    std::vector<int> runs;
    int i = 0;
    while((i < n)) {
        int j = (i + 1);
        while(((j < n) && (arr[(j - 1)] <= arr[j]))) {
            compare((j - 1), j);
            j++;
        }
        runs.push_back({i, j});
        i = j;
    }
    std::vector<int> temp(n, 0);
    while(((int)runs.size() > 1)) {
        int merged = 0;
        for(int r=0; ((r + 2) < (int)runs.size()); 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(((int)runs.size() - 2), ((int)runs.size() - 1));
        }
    }
}

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))) {
        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(int p=lo; p<hi; p++) {
        arr[p] = temp[p];
        write(p, arr[p]);
    }
    runs[a] = new int[] {lo, hi};
    runs_remove(b);
}

public void Sort(int[] arr, int n, dynamic stats) {
    var runs = new List<int>();
    int i = 0;
    while((i < n)) {
        int j = (i + 1);
        while(((j < n) && (arr[(j - 1)] <= arr[j]))) {
            compare((j - 1), j);
            j++;
        }
        runs.Add(new int[] {i, j});
        i = j;
    }
    int[] temp = new int[n];
    while((runs.Count > 1)) {
        int merged = false;
        for(int r=0; ((r + 2) < runs.Count); 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 = true;
                break;
            }
        }
        if(!merged) {
            merge((runs.Count - 2), (runs.Count - 1));
        }
    }
}

#include <stdio.h>
#include <stdlib.h>
void merge(int a, int b);

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))) {
        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(int p=lo; p<hi; p++) {
        arr[p] = temp[p];
        write(p, arr[p]);
    }
    runs[a] = {lo, hi};
    runs_remove(b);
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    int* runs = (int*)malloc(n * sizeof(int)); int runs_len = 0;
    int i = 0;
    while((i < n)) {
        int j = (i + 1);
        while(((j < n) && (arr[(j - 1)] <= arr[j]))) {
            compare((j - 1), j);
            j++;
        }
        runs[runs_len++] = {i, j};
        i = j;
    }
    int* temp = (int*)malloc((n) * sizeof(int));
    while((runs_len > 1)) {
        int merged = 0;
        for(int r=0; ((r + 2) < runs_len); 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((runs_len - 2), (runs_len - 1));
        }
    }
}