Drop-Merge Sort

function dropMergeSort(arr, stats) {
  const n = arr.length;
  if (n < 2) return;
  let inc = [0];
  for (let i = 1; i < n; i++) {
    if (arr[i] >= arr[inc[inc.length - 1]]) inc.push(i);
  }
  let incSet = new Set(inc);
  let dropped = [];
  let keptValues = inc.map(idx => arr[idx]);
  for (let i = 0; i < n; i++) {
    if (!incSet.has(i)) {
      dropped.push(arr[i]);
      arr[i] = -1;
      write(i, -1);
    }
  }
  for (let i = 1; i < dropped.length; i++) {
    let key = dropped[i], j = i - 1;
    while (j >= 0 && dropped[j] > key) {
      dropped[j + 1] = dropped[j];
      j--;
    }
    dropped[j + 1] = key;
  }
  let a = 0, b = 0, k = 0;
  while (a < keptValues.length && b < dropped.length) {
    if (keptValues[a] <= dropped[b]) {
      arr[k++] = keptValues[a++];
    } else {
      arr[k++] = dropped[b++];
    }
    write(k - 1, arr[k - 1]);
  }
  while (a < keptValues.length) {
    arr[k++] = keptValues[a++];
    write(k - 1, arr[k - 1]);
  }
  while (b < dropped.length) {
    arr[k++] = dropped[b++];
    write(k - 1, arr[k - 1]);
  }
  for (let i = 0; i < n; i++) markSorted(i);
}

def dropMergeSort(arr, stats):
    if (n < 2):
        return
    inc = [0]
    for i in range(1, n):
        if (arr[i] >= arr[inc[(len(inc) - 1)]]):
            inc.append(i)
    incSet = set(inc)
    dropped = []
    keptValues = [arr[idx] for idx in inc]
    for i in range(n):
        if not (i in incSet):
            dropped.append(arr[i])
            arr[i] = -1
            write(i, -1)
    for i in range(1, len(dropped)):
        key = dropped[i]
        j = (i - 1)
        while ((j >= 0) and (dropped[j] > key)):
            dropped[(j + 1)] = dropped[j]
            j -= 1
        dropped[(j + 1)] = key
    a = 0
    b = 0
    k = 0
    while ((a < len(keptValues)) and (b < len(dropped))):
        if (keptValues[a] <= dropped[b]):
            arr[((k := k + 1) - 1)] = keptValues[((a := a + 1) - 1)]
        else:
            arr[((k := k + 1) - 1)] = dropped[((b := b + 1) - 1)]
        write((k - 1), arr[(k - 1)])
    while (a < len(keptValues)):
        arr[((k := k + 1) - 1)] = keptValues[((a := a + 1) - 1)]
        write((k - 1), arr[(k - 1)])
    while (b < len(dropped)):
        arr[((k := k + 1) - 1)] = dropped[((b := b + 1) - 1)]
        write((k - 1), arr[(k - 1)])
    for i in range(n):
        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> inc = {0};
    for(int i=1; i<n; i++) {
        if((arr[i] >= arr[inc[((int)inc.size() - 1)]])) {
            inc.push_back(i);
        }
    }
    int incSet = 0;
    std::vector<int> dropped;
    std::vector<int> keptValues(n); for(int _mi=0;_mi<n;_mi++) { int idx=inc[_mi]; keptValues[_mi]=arr[idx]; }
    for(int i=0; i<n; i++) {
        if(!(incSet.count(i) > 0)) {
            dropped.push_back(arr[i]);
            arr[i] = -1;
            write(i, -1);
        }
    }
    for(int i=1; i<(int)dropped.size(); i++) {
        int key = dropped[i];
        int j = (i - 1);
        while(((j >= 0) && (dropped[j] > key))) {
            dropped[(j + 1)] = dropped[j];
            j--;
        }
        dropped[(j + 1)] = key;
    }
    int a = 0;
    int b = 0;
    int k = 0;
    while(((a < n) && (b < (int)dropped.size()))) {
        if((keptValues[a] <= dropped[b])) {
            arr[k++] = keptValues[a++];
        } else {
            arr[k++] = dropped[b++];
        }
        write((k - 1), arr[(k - 1)]);
    }
    while((a < n)) {
        arr[k++] = keptValues[a++];
        write((k - 1), arr[(k - 1)]);
    }
    while((b < (int)dropped.size())) {
        arr[k++] = dropped[b++];
        write((k - 1), arr[(k - 1)]);
    }
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        return;
    }
    var inc = new List<int> { 0 };
    for(int i=1; i<n; i++) {
        if((arr[i] >= arr[inc[(inc.Count - 1)]])) {
            inc.Add(i);
        }
    }
    int incSet = 0;
    var dropped = new List<int>();
    int[] keptValues = new int[n]; for(int _mi=0;_mi<n;_mi++) { int idx=inc[_mi]; keptValues[_mi]=arr[idx]; }
    for(int i=0; i<n; i++) {
        if(!incSet.Contains(i)) {
            dropped.Add(arr[i]);
            arr[i] = -1;
            write(i, -1);
        }
    }
    for(int i=1; i<dropped.Count; i++) {
        int key = dropped[i];
        int j = (i - 1);
        while(((j >= 0) && (dropped[j] > key))) {
            dropped[(j + 1)] = dropped[j];
            j--;
        }
        dropped[(j + 1)] = key;
    }
    int a = 0;
    int b = 0;
    int k = 0;
    while(((a < n) && (b < dropped.Count))) {
        if((keptValues[a] <= dropped[b])) {
            arr[k++] = keptValues[a++];
        } else {
            arr[k++] = dropped[b++];
        }
        write((k - 1), arr[(k - 1)]);
    }
    while((a < n)) {
        arr[k++] = keptValues[a++];
        write((k - 1), arr[(k - 1)]);
    }
    while((b < dropped.Count)) {
        arr[k++] = dropped[b++];
        write((k - 1), arr[(k - 1)]);
    }
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
}

#include <stdio.h>
#include <stdlib.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        return;
    }
    int* inc = (int*)malloc(n * sizeof(int)); int inc_len = 1;
    inc[0] = 0;
    for(int i=1; i<n; i++) {
        if((arr[i] >= arr[inc[(inc_len - 1)]])) {
            inc[inc_len++] = i;
        }
    }
    int incSet = 0;
    int* dropped = (int*)malloc(n * sizeof(int)); int dropped_len = 0;
    int* keptValues = (int*)malloc((n) * sizeof(int)); for(int _mi=0;_mi<n;_mi++) { int idx=inc[_mi]; keptValues[_mi]=arr[idx]; }
    for(int i=0; i<n; i++) {
        if(!incSet_has(i)) {
            dropped[dropped_len++] = arr[i];
            arr[i] = -1;
            write(i, -1);
        }
    }
    for(int i=1; i<dropped_len; i++) {
        int key = dropped[i];
        int j = (i - 1);
        while(((j >= 0) && (dropped[j] > key))) {
            dropped[(j + 1)] = dropped[j];
            j--;
        }
        dropped[(j + 1)] = key;
    }
    int a = 0;
    int b = 0;
    int k = 0;
    while(((a < n) && (b < dropped_len))) {
        if((keptValues[a] <= dropped[b])) {
            arr[k++] = keptValues[a++];
        } else {
            arr[k++] = dropped[b++];
        }
        write((k - 1), arr[(k - 1)]);
    }
    while((a < n)) {
        arr[k++] = keptValues[a++];
        write((k - 1), arr[(k - 1)]);
    }
    while((b < dropped_len)) {
        arr[k++] = dropped[b++];
        write((k - 1), arr[(k - 1)]);
    }
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
}