Stalin Sort

function stalinSort(arr, stats) {
  const n = arr.length;
  if (n < 2) return;
  const kept = [];
  const purged = [];
  for (let i = 0; i < n; i++) {
    const v = arr[i];
    if (kept.length === 0) {
      kept.push(v);
    } else {
      compare(i - 1, i);
      if (v >= kept[kept.length - 1]) kept.push(v); else purged.push(v);
    }
  }
  for (let i = 1; i < purged.length; i++) {
    const key = purged[i];
    let j = i - 1;
    while (j >= 0) {
      if (purged[j] <= key) break;
      purged[j + 1] = purged[j];
      j--;
    }
    purged[j + 1] = key;
  }
  const merged = [];
  let a = 0, b = 0;
  while (a < kept.length && b < purged.length) {
    if (kept[a] <= purged[b]) merged.push(kept[a++]); else merged.push(purged[b++]);
  }
  while (a < kept.length) merged.push(kept[a++]);
  while (b < purged.length) merged.push(purged[b++]);
  for (let i = 0; i < n; i++) {
    arr[i] = merged[i];
    write(i, merged[i]);
    markSorted(i);
  }
}

def stalinSort(arr, stats):
    if (n < 2):
        return
    kept = []
    purged = []
    for i in range(n):
        v = arr[i]
        if (len(kept) == 0):
            kept.append(v)
        else:
            compare((i - 1), i)
            if (v >= kept[(len(kept) - 1)]):
                kept.append(v)
            else:
                purged.append(v)
    for i in range(1, len(purged)):
        key = purged[i]
        j = (i - 1)
        while (j >= 0):
            if (purged[j] <= key):
                break
            purged[(j + 1)] = purged[j]
            j -= 1
        purged[(j + 1)] = key
    merged = []
    a = 0
    b = 0
    while ((a < len(kept)) and (b < len(purged))):
        if (kept[a] <= purged[b]):
            merged.append(kept[((a := a + 1) - 1)])
        else:
            merged.append(purged[((b := b + 1) - 1)])
    while (a < len(kept)):
        merged.append(kept[((a := a + 1) - 1)])
    while (b < len(purged)):
        merged.append(purged[((b := b + 1) - 1)])
    for i in range(n):
        arr[i] = merged[i]
        write(i, merged[i])
        markSorted(i)

#include <vector>
#include <algorithm>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        return;
    }
    std::vector<int> kept;
    std::vector<int> purged;
    for(int i=0; i<n; i++) {
        int v = arr[i];
        if(((int)kept.size() == 0)) {
            kept.push_back(v);
        } else {
            compare((i - 1), i);
            if((v >= kept[((int)kept.size() - 1)])) {
                kept.push_back(v);
            } else {
                purged.push_back(v);
            }
        }
    }
    for(int i=1; i<(int)purged.size(); i++) {
        int key = purged[i];
        int j = (i - 1);
        while((j >= 0)) {
            if((purged[j] <= key)) {
                break;
            }
            purged[(j + 1)] = purged[j];
            j--;
        }
        purged[(j + 1)] = key;
    }
    std::vector<int> merged;
    int a = 0;
    int b = 0;
    while(((a < (int)kept.size()) && (b < (int)purged.size()))) {
        if((kept[a] <= purged[b])) {
            merged.push_back(kept[a++]);
        } else {
            merged.push_back(purged[b++]);
        }
    }
    while((a < (int)kept.size())) {
        merged.push_back(kept[a++]);
    }
    while((b < (int)purged.size())) {
        merged.push_back(purged[b++]);
    }
    for(int i=0; i<n; i++) {
        arr[i] = merged[i];
        write(i, merged[i]);
        markSorted(i);
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        return;
    }
    var kept = new List<int>();
    var purged = new List<int>();
    for(int i=0; i<n; i++) {
        int v = arr[i];
        if((kept.Count == 0)) {
            kept.Add(v);
        } else {
            compare((i - 1), i);
            if((v >= kept[(kept.Count - 1)])) {
                kept.Add(v);
            } else {
                purged.Add(v);
            }
        }
    }
    for(int i=1; i<purged.Count; i++) {
        int key = purged[i];
        int j = (i - 1);
        while((j >= 0)) {
            if((purged[j] <= key)) {
                break;
            }
            purged[(j + 1)] = purged[j];
            j--;
        }
        purged[(j + 1)] = key;
    }
    var merged = new List<int>();
    int a = 0;
    int b = 0;
    while(((a < kept.Count) && (b < purged.Count))) {
        if((kept[a] <= purged[b])) {
            merged.Add(kept[a++]);
        } else {
            merged.Add(purged[b++]);
        }
    }
    while((a < kept.Count)) {
        merged.Add(kept[a++]);
    }
    while((b < purged.Count)) {
        merged.Add(purged[b++]);
    }
    for(int i=0; i<n; i++) {
        arr[i] = merged[i];
        write(i, merged[i]);
        markSorted(i);
    }
}

#include <stdio.h>
#include <stdlib.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        return;
    }
    int* kept = (int*)malloc(n * sizeof(int)); int kept_len = 0;
    int* purged = (int*)malloc(n * sizeof(int)); int purged_len = 0;
    for(int i=0; i<n; i++) {
        int v = arr[i];
        if((kept_len == 0)) {
            kept[kept_len++] = v;
        } else {
            compare((i - 1), i);
            if((v >= kept[(kept_len - 1)])) {
                kept[kept_len++] = v;
            } else {
                purged[purged_len++] = v;
            }
        }
    }
    for(int i=1; i<purged_len; i++) {
        int key = purged[i];
        int j = (i - 1);
        while((j >= 0)) {
            if((purged[j] <= key)) {
                break;
            }
            purged[(j + 1)] = purged[j];
            j--;
        }
        purged[(j + 1)] = key;
    }
    int* merged = (int*)malloc(n * sizeof(int)); int merged_len = 0;
    int a = 0;
    int b = 0;
    while(((a < kept_len) && (b < purged_len))) {
        if((kept[a] <= purged[b])) {
            merged[merged_len++] = kept[a++];
        } else {
            merged[merged_len++] = purged[b++];
        }
    }
    while((a < kept_len)) {
        merged[merged_len++] = kept[a++];
    }
    while((b < purged_len)) {
        merged[merged_len++] = purged[b++];
    }
    for(int i=0; i<n; i++) {
        arr[i] = merged[i];
        write(i, merged[i]);
        markSorted(i);
    }
}