Strand Sort

function strandSort(arr, stats) {
  const n = arr.length;
  if (n <= 1) return;
  let input = arr.slice();
  let output = [];
  function mergeArrays(a, b) {
    const result = [];
    let i = 0, j = 0;
    while (i < a.length && j < b.length) {
      if (a[i] <= b[j]) result.push(a[i++]); else result.push(b[j++]);
    }
    while (i < a.length) {
      result.push(a[i++]);
    }
    while (j < b.length) {
      result.push(b[j++]);
    }
    return result;
  }
  let pass = 0;
  while (input.length > 0) {
    const strand = [input[0]];
    const remaining = [];
    for (let i = 1; i < input.length; i++) {
      if (input[i] >= strand[strand.length - 1]) {
        strand.push(input[i]);
      } else {
        remaining.push(input[i]);
      }
    }
    input = remaining;
    output = mergeArrays(output, strand);
    pass++;
    for (let i = 0; i < output.length; i++) {
      arr[i] = output[i];
      write(i, output[i]);
    }
    checkpoint(pass, pass + input.length);
  }
  for (let i = 0; i < n; i++) markSorted(i);
}

def strandSort(arr, stats):
    def mergeArrays(a, b):
        result = []
        i = 0
        j = 0
        while ((i < len(a)) and (j < len(b))):
            if (a[i] <= b[j]):
                result.append(a[((i := i + 1) - 1)])
            else:
                result.append(b[((j := j + 1) - 1)])
        while (i < len(a)):
            result.append(a[((i := i + 1) - 1)])
        while (j < len(b)):
            result.append(b[((j := j + 1) - 1)])
        return result

    if (n <= 1):
        return
    input = arr[:]
    output = []
    pass = 0
    while (len(input) > 0):
        strand = [input[0]]
        remaining = []
        for i in range(1, len(input)):
            if (input[i] >= strand[(len(strand) - 1)]):
                strand.append(input[i])
            else:
                remaining.append(input[i])
        input = remaining
        output = mergeArrays(output, strand)
        pass += 1
        for i in range(len(output)):
            arr[i] = output[i]
            write(i, output[i])
        checkpoint(pass, (pass + len(input)))
    for i in range(n):
        markSorted(i)

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

int mergeArrays(int a, int b) {
    std::vector<int> result;
    int i = 0;
    int j = 0;
    while(((i < n) && (j < n))) {
        if((a[i] <= b[j])) {
            result.push_back(a[i++]);
        } else {
            result.push_back(b[j++]);
        }
    }
    while((i < n)) {
        result.push_back(a[i++]);
    }
    while((j < n)) {
        result.push_back(b[j++]);
    }
    return result;
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n <= 1)) {
        return;
    }
    int _input_len = n - (0);
    std::vector<int> input(arr.begin() + (0), arr.begin() + (n));
    std::vector<int> output;
    int pass = 0;
    while((_input_len > 0)) {
        std::vector<int> strand = {input[0]};
        std::vector<int> remaining;
        for(int i=1; i<_input_len; i++) {
            if((input[i] >= strand[((int)strand.size() - 1)])) {
                strand.push_back(input[i]);
            } else {
                remaining.push_back(input[i]);
            }
        }
        input = remaining;
        output = mergeArrays(output, strand);
        pass++;
        for(int i=0; i<(int)output.size(); i++) {
            arr[i] = output[i];
            write(i, output[i]);
        }
        checkpoint(pass, (pass + _input_len));
    }
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
}

int mergeArrays(int a, int b) {
    var result = new List<int>();
    int i = 0;
    int j = 0;
    while(((i < n) && (j < n))) {
        if((a[i] <= b[j])) {
            result.Add(a[i++]);
        } else {
            result.Add(b[j++]);
        }
    }
    while((i < n)) {
        result.Add(a[i++]);
    }
    while((j < n)) {
        result.Add(b[j++]);
    }
    return result;
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n <= 1)) {
        return;
    }
    int _input_len = n - (0);
    int[] input = new int[_input_len];
    Array.Copy(arr, 0, input, 0, _input_len);
    var output = new List<int>();
    int pass = 0;
    while((_input_len > 0)) {
        var strand = new List<int> { input[0] };
        var remaining = new List<int>();
        for(int i=1; i<_input_len; i++) {
            if((input[i] >= strand[(strand.Count - 1)])) {
                strand.Add(input[i]);
            } else {
                remaining.Add(input[i]);
            }
        }
        input = remaining;
        output = mergeArrays(output, strand);
        pass++;
        for(int i=0; i<output.Count; i++) {
            arr[i] = output[i];
            write(i, output[i]);
        }
        checkpoint(pass, (pass + _input_len));
    }
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
}

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

int mergeArrays(int a, int b) {
    int* result = (int*)malloc(n * sizeof(int)); int result_len = 0;
    int i = 0;
    int j = 0;
    while(((i < n) && (j < n))) {
        if((a[i] <= b[j])) {
            result[result_len++] = a[i++];
        } else {
            result[result_len++] = b[j++];
        }
    }
    while((i < n)) {
        result[result_len++] = a[i++];
    }
    while((j < n)) {
        result[result_len++] = b[j++];
    }
    return result;
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n <= 1)) {
        return;
    }
    int _input_len = n - (0);
    int* input = (int*)malloc((_input_len) * sizeof(int));
    for(int _ci=0;_ci<_input_len;_ci++) input[_ci]=arr[(0)+_ci];
    int* output = (int*)malloc(n * sizeof(int)); int output_len = 0;
    int pass = 0;
    while((_input_len > 0)) {
        int* strand = (int*)malloc(n * sizeof(int)); int strand_len = 1;
        strand[0] = input[0];
        int* remaining = (int*)malloc(n * sizeof(int)); int remaining_len = 0;
        for(int i=1; i<_input_len; i++) {
            if((input[i] >= strand[(strand_len - 1)])) {
                strand[strand_len++] = input[i];
            } else {
                remaining[remaining_len++] = input[i];
            }
        }
        input = remaining;
        output = mergeArrays(output, strand);
        pass++;
        for(int i=0; i<output_len; i++) {
            arr[i] = output[i];
            write(i, output[i]);
        }
        checkpoint(pass, (pass + _input_len));
    }
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
}