Replacement Selection Sort

function replacementSelectionSort(arr, stats) {
  const n = arr.length;
  if (n < 2) return;
  const source = [...arr];
  const heapSize = Math.min(n, Math.max(4, Math.floor(Math.sqrt(n))));
  let heap = source.slice(0, heapSize);
  let inputIdx = heapSize;
  const runs = [];
  let currentRun = [];
  let previewWrite = 0;
  const siftDown = (h, i) => {
    while (true) {
      let smallest = i;
      const l = i * 2 + 1;
      const r = l + 1;
      if (l < h.length) {
        if (h[l] < h[smallest]) smallest = l;
      }
      if (r < h.length) {
        if (h[r] < h[smallest]) smallest = r;
      }
      if (smallest === i) break;
      const t = h[i];
      h[i] = h[smallest];
      h[smallest] = t;
      i = smallest;
    }
  };
  const heapify = h => {
    for (let i = (h.length >> 1) - 1; i >= 0; i--) siftDown(h, i);
  };
  heapify(heap);
  let frozen = [];
  let lastOut = -Infinity;
  while (heap.length) {
    const minVal = heap[0];
    currentRun.push(minVal);
    lastOut = minVal;
    arr[previewWrite] = minVal;
    write(previewWrite, minVal);
    previewWrite++;
    if (inputIdx < n) {
      const next = source[inputIdx++];
      if (next >= lastOut) heap[0] = next; else {
        heap[0] = heap[heap.length - 1];
        heap.pop();
        frozen.push(next);
      }
    } else {
      heap[0] = heap[heap.length - 1];
      heap.pop();
    }
    if (heap.length) siftDown(heap, 0);
    if (!heap.length && frozen.length) {
      runs.push(currentRun);
      currentRun = [];
      heap = frozen;
      frozen = [];
      heapify(heap);
      lastOut = -Infinity;
    }
  }
  if (currentRun.length) runs.push(currentRun);
  const ptr = new Array(runs.length).fill(0);
  for (let k = 0; k < n; k++) {
    let ri = -1;
    let best = 0;
    for (let r = 0; r < runs.length; r++) {
      if (ptr[r] >= runs[r].length) continue;
      const v = runs[r][ptr[r]];
      if (ri === -1 || v < best) {
        if (ri !== -1) stats.comparisons++;
        ri = r;
        best = v;
      }
    }
    arr[k] = best;
    ptr[ri]++;
    write(k, arr[k]);
    markSorted(k);
  }
}

def replacementSelectionSort(arr, stats):
    def siftDown(h, i):
        while True:
            smallest = i
            l = ((i * 2) + 1)
            r = (l + 1)
            if (l < len(h)):
                if (h[l] < h[smallest]):
                    smallest = l
            if (r < len(h)):
                if (h[r] < h[smallest]):
                    smallest = r
            if (smallest == i):
                break
            t = h[i]
            h[i] = h[smallest]
            h[smallest] = t
            i = smallest

    def heapify(h):
        for i in range(((len(h) >> 1) - 1), (0 - 1), -1):
            siftDown(h, i)

    if (n < 2):
        return
    source = [*arr]
    heapSize = (n if n <= (4 if 4 >= int(int(n ** 0.5)) else int(int(n ** 0.5))) else (4 if 4 >= int(int(n ** 0.5)) else int(int(n ** 0.5))))
    heap = source[0:heapSize]
    inputIdx = heapSize
    runs = []
    currentRun = []
    previewWrite = 0
    heapify(heap)
    frozen = []
    lastOut = -float('inf')
    while len(heap):
        minVal = heap[0]
        currentRun.append(minVal)
        lastOut = minVal
        arr[previewWrite] = minVal
        write(previewWrite, minVal)
        previewWrite += 1
        if (inputIdx < n):
            next = source[((inputIdx := inputIdx + 1) - 1)]
            if (next >= lastOut):
                heap[0] = next
            else:
                heap[0] = heap[(len(heap) - 1)]
                heap.pop()
                frozen.append(next)
        else:
            heap[0] = heap[(len(heap) - 1)]
            heap.pop()
        if len(heap):
            siftDown(heap, 0)
        if (not len(heap) and len(frozen)):
            runs.append(currentRun)
            currentRun = []
            heap = frozen
            frozen = []
            heapify(heap)
            lastOut = -float('inf')
    if len(currentRun):
        runs.append(currentRun)
    ptr = [0] * len(runs)
    for k in range(n):
        ri = -1
        best = 0
        for r in range(len(runs)):
            if (ptr[r] >= len(runs[r])):
                continue
            v = runs[r][ptr[r]]
            if ((ri == -1) or (v < best)):
                if (ri != -1):
                    pass
                ri = r
                best = v
        arr[k] = best
        ptr[ri] += 1
        write(k, arr[k])
        markSorted(k)

#include <vector>
#include <algorithm>
#include <cmath>
void siftDown(int h, int i);
void heapify(int h);

void siftDown(int h, int i) {
    while(1) {
        int smallest = i;
        int l = ((i * 2) + 1);
        int r = (l + 1);
        if((l < n)) {
            if((h[l] < h[smallest])) {
                smallest = l;
            }
        }
        if((r < n)) {
            if((h[r] < h[smallest])) {
                smallest = r;
            }
        }
        if((smallest == i)) {
            break;
        }
        int t = h[i];
        h[i] = h[smallest];
        h[smallest] = t;
        i = smallest;
    }
}

void heapify(int h) {
    for(int i=((n >> 1) - 1); i>(0 - 1); i--) {
        siftDown(h, i);
    }
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        return;
    }
    std::vector<int> source = {arr};
    int heapSize = ((n) < (((4) > ((int)std::floor((int)std::sqrt(n))) ? (4) : ((int)std::floor((int)std::sqrt(n))))) ? (n) : (((4) > ((int)std::floor((int)std::sqrt(n))) ? (4) : ((int)std::floor((int)std::sqrt(n))))));
    int _heap_len = heapSize - (0);
    std::vector<int> heap(source.begin() + (0), source.begin() + (heapSize));
    int inputIdx = heapSize;
    std::vector<int> runs;
    std::vector<int> currentRun;
    int previewWrite = 0;
    heapify(heap);
    std::vector<int> frozen;
    int lastOut = -2147483647;
    while(_heap_len) {
        int minVal = heap[0];
        currentRun.push_back(minVal);
        lastOut = minVal;
        arr[previewWrite] = minVal;
        write(previewWrite, minVal);
        previewWrite++;
        if((inputIdx < n)) {
            int next = source[inputIdx++];
            if((next >= lastOut)) {
                heap[0] = next;
            } else {
                heap[0] = heap[(_heap_len - 1)];
                heap.back();
                frozen.push_back(next);
            }
        } else {
            heap[0] = heap[(_heap_len - 1)];
            heap.back();
        }
        if(_heap_len) {
            siftDown(heap, 0);
        }
        if(((!_heap_len) != 0 ? ((int)frozen.size()) : (!_heap_len))) {
            runs.push_back(currentRun);
            currentRun = {};
            heap = frozen;
            frozen = {};
            heapify(heap);
            lastOut = -2147483647;
        }
    }
    if((int)currentRun.size()) {
        runs.push_back(currentRun);
    }
    std::vector<int> ptr((int)runs.size(), 0);
    for(int k=0; k<n; k++) {
        int ri = -1;
        int best = 0;
        for(int r=0; r<(int)runs.size(); r++) {
            if((ptr[r] >= n)) {
                continue;
            }
            int v = runs[r][ptr[r]];
            if(((ri == -1) || (v < best))) {
                if((ri != -1)) {
                }
                ri = r;
                best = v;
            }
        }
        arr[k] = best;
        ptr[ri]++;
        write(k, arr[k]);
        markSorted(k);
    }
}

void siftDown(int h, int i) {
    while(true) {
        int smallest = i;
        int l = ((i * 2) + 1);
        int r = (l + 1);
        if((l < n)) {
            if((h[l] < h[smallest])) {
                smallest = l;
            }
        }
        if((r < n)) {
            if((h[r] < h[smallest])) {
                smallest = r;
            }
        }
        if((smallest == i)) {
            break;
        }
        int t = h[i];
        h[i] = h[smallest];
        h[smallest] = t;
        i = smallest;
    }
}

void heapify(int h) {
    for(int i=((n >> 1) - 1); i>(0 - 1); i--) {
        siftDown(h, i);
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        return;
    }
    var source = new List<int> { arr };
    int heapSize = Math.Min(n, Math.Max(4, (int)Math.Floor((double)(int)Math.Sqrt(n))));
    int _heap_len = heapSize - (0);
    int[] heap = new int[_heap_len];
    Array.Copy(source, 0, heap, 0, _heap_len);
    int inputIdx = heapSize;
    var runs = new List<int>();
    var currentRun = new List<int>();
    int previewWrite = 0;
    heapify(heap);
    var frozen = new List<int>();
    int lastOut = -int.MaxValue;
    while(_heap_len) {
        int minVal = heap[0];
        currentRun.Add(minVal);
        lastOut = minVal;
        arr[previewWrite] = minVal;
        write(previewWrite, minVal);
        previewWrite++;
        if((inputIdx < n)) {
            int next = source[inputIdx++];
            if((next >= lastOut)) {
                heap[0] = next;
            } else {
                heap[0] = heap[(_heap_len - 1)];
                heap[--heap_len];
                frozen.Add(next);
            }
        } else {
            heap[0] = heap[(_heap_len - 1)];
            heap[--heap_len];
        }
        if(_heap_len) {
            siftDown(heap, 0);
        }
        if(((!_heap_len) != 0 ? (frozen.Count) : (!_heap_len))) {
            runs.Add(currentRun);
            currentRun = new int[] {};
            heap = frozen;
            frozen = new int[] {};
            heapify(heap);
            lastOut = -int.MaxValue;
        }
    }
    if(currentRun.Count) {
        runs.Add(currentRun);
    }
    int[] ptr = new int[runs.Count];
    for(int k=0; k<n; k++) {
        int ri = -1;
        int best = 0;
        for(int r=0; r<runs.Count; r++) {
            if((ptr[r] >= n)) {
                continue;
            }
            int v = runs[r][ptr[r]];
            if(((ri == -1) || (v < best))) {
                if((ri != -1)) {
                }
                ri = r;
                best = v;
            }
        }
        arr[k] = best;
        ptr[ri]++;
        write(k, arr[k]);
        markSorted(k);
    }
}

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
void siftDown(int h, int i);
void heapify(int h);

void siftDown(int h, int i) {
    while(1) {
        int smallest = i;
        int l = ((i * 2) + 1);
        int r = (l + 1);
        if((l < n)) {
            if((h[l] < h[smallest])) {
                smallest = l;
            }
        }
        if((r < n)) {
            if((h[r] < h[smallest])) {
                smallest = r;
            }
        }
        if((smallest == i)) {
            break;
        }
        int t = h[i];
        h[i] = h[smallest];
        h[smallest] = t;
        i = smallest;
    }
}

void heapify(int h) {
    for(int i=((n >> 1) - 1); i>(0 - 1); i--) {
        siftDown(h, i);
    }
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        return;
    }
    int* source = (int*)malloc(n * sizeof(int)); int source_len = 1;
    source[0] = arr;
    int heapSize = ((n) < (((4) > ((int)floor((int)sqrt(n))) ? (4) : ((int)floor((int)sqrt(n))))) ? (n) : (((4) > ((int)floor((int)sqrt(n))) ? (4) : ((int)floor((int)sqrt(n))))));
    int _heap_len = heapSize - (0);
    int* heap = (int*)malloc((_heap_len) * sizeof(int));
    for(int _ci=0;_ci<_heap_len;_ci++) heap[_ci]=source[(0)+_ci];
    int inputIdx = heapSize;
    int* runs = (int*)malloc(n * sizeof(int)); int runs_len = 0;
    int* currentRun = (int*)malloc(n * sizeof(int)); int currentRun_len = 0;
    int previewWrite = 0;
    heapify(heap);
    int* frozen = (int*)malloc(n * sizeof(int)); int frozen_len = 0;
    int lastOut = -2147483647;
    while(_heap_len) {
        int minVal = heap[0];
        currentRun[currentRun_len++] = minVal;
        lastOut = minVal;
        arr[previewWrite] = minVal;
        write(previewWrite, minVal);
        previewWrite++;
        if((inputIdx < n)) {
            int next = source[inputIdx++];
            if((next >= lastOut)) {
                heap[0] = next;
            } else {
                heap[0] = heap[(_heap_len - 1)];
                heap[--heap_len];
                frozen[frozen_len++] = next;
            }
        } else {
            heap[0] = heap[(_heap_len - 1)];
            heap[--heap_len];
        }
        if(_heap_len) {
            siftDown(heap, 0);
        }
        if(((!_heap_len) != 0 ? (frozen_len) : (!_heap_len))) {
            runs[runs_len++] = currentRun;
            currentRun = {};
            heap = frozen;
            frozen = {};
            heapify(heap);
            lastOut = -2147483647;
        }
    }
    if(currentRun_len) {
        runs[runs_len++] = currentRun;
    }
    int* ptr = (int*)malloc((runs_len) * sizeof(int)); memset(ptr, 0, (runs_len) * sizeof(int));
    for(int k=0; k<n; k++) {
        int ri = -1;
        int best = 0;
        for(int r=0; r<runs_len; r++) {
            if((ptr[r] >= n)) {
                continue;
            }
            int v = runs[r][ptr[r]];
            if(((ri == -1) || (v < best))) {
                if((ri != -1)) {
                }
                ri = r;
                best = v;
            }
        }
        arr[k] = best;
        ptr[ri]++;
        write(k, arr[k]);
        markSorted(k);
    }
}