Loser Tree Sort

function loserTreeSort(arr, stats) {
  const n = arr.length;
  if (n < 2) return;
  const runLen = Math.max(2, Math.floor(Math.sqrt(n)));
  for (let lo = 0; lo < n; lo += runLen) {
    const hi = Math.min(lo + runLen, n);
    for (let i = lo + 1; i < hi; i++) {
      const key = arr[i];
      let j = i - 1;
      while (j >= lo && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
      }
      arr[j + 1] = key;
    }
  }
  let runs = 0;
  for (let lo = 0; lo < n; lo += runLen) {
    runs++;
  }
  const head = new Array(runs).fill(0);
  const end = new Array(runs).fill(0);
  let r = 0;
  for (let lo = 0; lo < n; lo += runLen) {
    head[r] = lo;
    end[r] = Math.min(lo + runLen, n);
    r++;
  }
  const heap = new Array(runs).fill(0);
  let hs = 0;
  for (let t = 0; t < runs; t++) {
    heap[hs] = t;
    let c = hs;
    hs++;
    while (c > 0) {
      const par = (c - 1) >> 1;
      if (arr[head[heap[par]]] <= arr[head[heap[c]]]) break;
      const tmp = heap[par];
      heap[par] = heap[c];
      heap[c] = tmp;
      c = par;
    }
  }
  const output = new Array(n).fill(0);
  for (let o = 0; o < n; o++) {
    const run = heap[0];
    output[o] = arr[head[run]];
    head[run]++;
    if (head[run] >= end[run]) {
      hs--;
      heap[0] = heap[hs];
    }
    let c = 0;
    while (true) {
      const l = 2 * c + 1;
      const rr = 2 * c + 2;
      let small = c;
      if (l < hs && arr[head[heap[l]]] < arr[head[heap[small]]]) small = l;
      if (rr < hs && arr[head[heap[rr]]] < arr[head[heap[small]]]) small = rr;
      if (small === c) break;
      const tmp = heap[c];
      heap[c] = heap[small];
      heap[small] = tmp;
      c = small;
    }
  }
  for (let i = 0; i < n; i++) {
    arr[i] = output[i];
  }
}

def sort(arr, n, stats):
    if (n < 2):
        return
    runLen = max(2, int(int(n ** 0.5)))
    for lo in range(0, n, runLen):
        hi = min((lo + runLen), n)
        for i in range((lo + 1), hi):
            key = arr[i]
            j = (i - 1)
            while ((j >= lo) and (arr[j] > key)):
                arr[(j + 1)] = arr[j]
                j -= 1
            arr[(j + 1)] = key
    runs = 0
    for lo in range(0, n, runLen):
        runs += 1
    head = [0] * runs
    end = [0] * runs
    r = 0
    for lo in range(0, n, runLen):
        head[r] = lo
        end[r] = min((lo + runLen), n)
        r += 1
    heap = [0] * runs
    hs = 0
    for t in range(runs):
        heap[hs] = t
        c = hs
        hs += 1
        while (c > 0):
            par = ((c - 1) >> 1)
            if (arr[head[heap[par]]] <= arr[head[heap[c]]]):
                break
            heap[par], heap[c] = heap[c], heap[par]
            c = par
    output = [0] * n
    for o in range(n):
        run = heap[0]
        output[o] = arr[head[run]]
        head[run] += 1
        if (head[run] >= end[run]):
            hs -= 1
            heap[0] = heap[hs]
        c = 0
        while True:
            l = ((2 * c) + 1)
            rr = ((2 * c) + 2)
            small = c
            if ((l < hs) and (arr[head[heap[l]]] < arr[head[heap[small]]])):
                small = l
            if ((rr < hs) and (arr[head[heap[rr]]] < arr[head[heap[small]]])):
                small = rr
            if (small == c):
                break
            heap[c], heap[small] = heap[small], heap[c]
            c = small
    for i in range(n):
        arr[i] = output[i]

#include <vector>
#include <algorithm>
#include <cmath>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        return;
    }
    int runLen = ((2) > ((int)std::floor((int)std::sqrt(n))) ? (2) : ((int)std::floor((int)std::sqrt(n))));
    for(int lo=0; lo<n; lo+=runLen) {
        int hi = (((lo + runLen)) < (n) ? ((lo + runLen)) : (n));
        for(int i=(lo + 1); i<hi; i++) {
            int key = arr[i];
            int j = (i - 1);
            while(((j >= lo) && (arr[j] > key))) {
                arr[(j + 1)] = arr[j];
                j--;
            }
            arr[(j + 1)] = key;
        }
    }
    int runs = 0;
    for(int lo=0; lo<n; lo+=runLen) {
        runs++;
    }
    std::vector<int> head(runs, 0);
    std::vector<int> end(runs, 0);
    int r = 0;
    for(int lo=0; lo<n; lo+=runLen) {
        head[r] = lo;
        end[r] = (((lo + runLen)) < (n) ? ((lo + runLen)) : (n));
        r++;
    }
    std::vector<int> heap(runs, 0);
    int hs = 0;
    for(int t=0; t<runs; t++) {
        heap[hs] = t;
        int c = hs;
        hs++;
        while((c > 0)) {
            int par = ((c - 1) >> 1);
            if((arr[head[heap[par]]] <= arr[head[heap[c]]])) {
                break;
            }
            std::swap(heap[par], heap[c]);
            c = par;
        }
    }
    std::vector<int> output(n, 0);
    for(int o=0; o<n; o++) {
        int run = heap[0];
        output[o] = arr[head[run]];
        head[run]++;
        if((head[run] >= end[run])) {
            hs--;
            heap[0] = heap[hs];
        }
        int c = 0;
        while(1) {
            int l = ((2 * c) + 1);
            int rr = ((2 * c) + 2);
            int small = c;
            if(((l < hs) && (arr[head[heap[l]]] < arr[head[heap[small]]]))) {
                small = l;
            }
            if(((rr < hs) && (arr[head[heap[rr]]] < arr[head[heap[small]]]))) {
                small = rr;
            }
            if((small == c)) {
                break;
            }
            std::swap(heap[c], heap[small]);
            c = small;
        }
    }
    for(int i=0; i<n; i++) {
        arr[i] = output[i];
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        return;
    }
    int runLen = Math.Max(2, (int)Math.Floor((double)(int)Math.Sqrt(n)));
    for(int lo=0; lo<n; lo+=runLen) {
        int hi = Math.Min((lo + runLen), n);
        for(int i=(lo + 1); i<hi; i++) {
            int key = arr[i];
            int j = (i - 1);
            while(((j >= lo) && (arr[j] > key))) {
                arr[(j + 1)] = arr[j];
                j--;
            }
            arr[(j + 1)] = key;
        }
    }
    int runs = 0;
    for(int lo=0; lo<n; lo+=runLen) {
        runs++;
    }
    int[] head = new int[runs];
    int[] end = new int[runs];
    int r = 0;
    for(int lo=0; lo<n; lo+=runLen) {
        head[r] = lo;
        end[r] = Math.Min((lo + runLen), n);
        r++;
    }
    int[] heap = new int[runs];
    int hs = 0;
    for(int t=0; t<runs; t++) {
        heap[hs] = t;
        int c = hs;
        hs++;
        while((c > 0)) {
            int par = ((c - 1) >> 1);
            if((arr[head[heap[par]]] <= arr[head[heap[c]]])) {
                break;
            }
            { int _t = heap[par]; heap[par] = heap[c]; heap[c] = _t; }
            c = par;
        }
    }
    int[] output = new int[n];
    for(int o=0; o<n; o++) {
        int run = heap[0];
        output[o] = arr[head[run]];
        head[run]++;
        if((head[run] >= end[run])) {
            hs--;
            heap[0] = heap[hs];
        }
        int c = 0;
        while(true) {
            int l = ((2 * c) + 1);
            int rr = ((2 * c) + 2);
            int small = c;
            if(((l < hs) && (arr[head[heap[l]]] < arr[head[heap[small]]]))) {
                small = l;
            }
            if(((rr < hs) && (arr[head[heap[rr]]] < arr[head[heap[small]]]))) {
                small = rr;
            }
            if((small == c)) {
                break;
            }
            { int _t = heap[c]; heap[c] = heap[small]; heap[small] = _t; }
            c = small;
        }
    }
    for(int i=0; i<n; i++) {
        arr[i] = output[i];
    }
}

#include <stdio.h>
#include <string.h>
#include <math.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        return;
    }
    int runLen = ((2) > ((int)floor((int)sqrt(n))) ? (2) : ((int)floor((int)sqrt(n))));
    for(int lo=0; lo<n; lo+=runLen) {
        int hi = (((lo + runLen)) < (n) ? ((lo + runLen)) : (n));
        for(int i=(lo + 1); i<hi; i++) {
            int key = arr[i];
            int j = (i - 1);
            while(((j >= lo) && (arr[j] > key))) {
                arr[(j + 1)] = arr[j];
                j--;
            }
            arr[(j + 1)] = key;
        }
    }
    int runs = 0;
    for(int lo=0; lo<n; lo+=runLen) {
        runs++;
    }
    int head[runs]; memset(head, 0, sizeof(head));
    int end[runs]; memset(end, 0, sizeof(end));
    int r = 0;
    for(int lo=0; lo<n; lo+=runLen) {
        head[r] = lo;
        end[r] = (((lo + runLen)) < (n) ? ((lo + runLen)) : (n));
        r++;
    }
    int heap[runs]; memset(heap, 0, sizeof(heap));
    int hs = 0;
    for(int t=0; t<runs; t++) {
        heap[hs] = t;
        int c = hs;
        hs++;
        while((c > 0)) {
            int par = ((c - 1) >> 1);
            if((arr[head[heap[par]]] <= arr[head[heap[c]]])) {
                break;
            }
            { int _t = heap[par]; heap[par] = heap[c]; heap[c] = _t; }
            c = par;
        }
    }
    int output[n]; memset(output, 0, sizeof(output));
    for(int o=0; o<n; o++) {
        int run = heap[0];
        output[o] = arr[head[run]];
        head[run]++;
        if((head[run] >= end[run])) {
            hs--;
            heap[0] = heap[hs];
        }
        int c = 0;
        while(1) {
            int l = ((2 * c) + 1);
            int rr = ((2 * c) + 2);
            int small = c;
            if(((l < hs) && (arr[head[heap[l]]] < arr[head[heap[small]]]))) {
                small = l;
            }
            if(((rr < hs) && (arr[head[heap[rr]]] < arr[head[heap[small]]]))) {
                small = rr;
            }
            if((small == c)) {
                break;
            }
            { int _t = heap[c]; heap[c] = heap[small]; heap[small] = _t; }
            c = small;
        }
    }
    for(int i=0; i<n; i++) {
        arr[i] = output[i];
    }
}