Strand Sort

pick a language to open the code

def strand_sort(a):
    rest = list(a)
    out = []
    while rest:
        strand = [rest.pop(0)]
        i = 0
        while i < len(rest):
            if rest[i] >= strand[-1]:
                strand.append(rest.pop(i))
            else:
                i += 1
        merged = []
        while out and strand:
            merged.append(out.pop(0) if out[0] <= strand[0] else strand.pop(0))
        merged.extend(out)
        merged.extend(strand)
        out = merged
    a[:] = out

function strandSort(a) {
  const rest = a.slice();
  let out = [];
  while (rest.length > 0) {
    const strand = [rest.shift()];
    let i = 0;
    while (i < rest.length) {
      if (rest[i] >= strand.at(-1)) strand.push(rest.splice(i, 1)[0]);
      else i++;
    }
    const merged = [];
    while (out.length > 0 && strand.length > 0) {
      merged.push(out[0] <= strand[0] ? out.shift() : strand.shift());
    }
    out = merged.concat(out, strand);
  }
  for (let i = 0; i < a.length; i++) a[i] = out[i];
}

void strand_sort(int a[], int n) {
    int* out = malloc(sizeof(int) * (n + 1));
    int* strand = malloc(sizeof(int) * (n + 1));
    int* merged = malloc(sizeof(int) * (n + 1));
    int rest = n, done = 0;
    while (rest > 0) {
        int taken = 0, keep = 0;
        for (int i = 0; i < rest; i++) {
            if (taken == 0 || a[i] >= strand[taken - 1]) strand[taken++] = a[i];
            else a[keep++] = a[i];
        }
        rest = keep;
        int i = 0, j = 0, k = 0;
        while (i < done && j < taken) {
            merged[k++] = out[i] <= strand[j] ? out[i++] : strand[j++];
        }
        while (i < done) merged[k++] = out[i++];
        while (j < taken) merged[k++] = strand[j++];
        done = k;
        memcpy(out, merged, sizeof(int) * k);
    }
    memcpy(a, out, sizeof(int) * n);
    free(out);
    free(strand);
    free(merged);
}

void strand_sort(std::vector<int>& a) {
    std::vector<int> rest = a, out;
    while (!rest.empty()) {
        std::vector<int> strand{rest.front()}, left;
        for (size_t i = 1; i < rest.size(); i++) {
            if (rest[i] >= strand.back()) strand.push_back(rest[i]);
            else left.push_back(rest[i]);
        }
        rest = left;
        size_t at = out.size();
        out.insert(out.end(), strand.begin(), strand.end());
        std::inplace_merge(out.begin(), out.begin() + at, out.end());
    }
    a = out;
}

static void StrandSort(int[] a) {
    var rest = new List<int>(a);
    var sorted = new List<int>();
    while (rest.Count > 0) {
        var strand = new List<int>();
        var left = new List<int>();
        foreach (int value in rest) {
            if (strand.Count == 0 || value >= strand[^1]) strand.Add(value);
            else left.Add(value);
        }
        rest = left;
        var merged = new List<int>();
        int i = 0, j = 0;
        while (i < sorted.Count && j < strand.Count) {
            merged.Add(sorted[i] <= strand[j] ? sorted[i++] : strand[j++]);
        }
        while (i < sorted.Count) merged.Add(sorted[i++]);
        while (j < strand.Count) merged.Add(strand[j++]);
        sorted = merged;
    }
    sorted.CopyTo(a);
}

static void strandSort(int[] a) {
    List<Integer> rest = new ArrayList<>();
    for (int value : a) rest.add(value);
    List<Integer> out = new ArrayList<>();
    while (!rest.isEmpty()) {
        List<Integer> strand = new ArrayList<>();
        List<Integer> left = new ArrayList<>();
        for (int value : rest) {
            if (strand.isEmpty() || value >= strand.get(strand.size() - 1)) {
                strand.add(value);
            } else {
                left.add(value);
            }
        }
        rest = left;
        List<Integer> merged = new ArrayList<>();
        int i = 0, j = 0;
        while (i < out.size() && j < strand.size()) {
            if (out.get(i) <= strand.get(j)) merged.add(out.get(i++));
            else merged.add(strand.get(j++));
        }
        while (i < out.size()) merged.add(out.get(i++));
        while (j < strand.size()) merged.add(strand.get(j++));
        out = merged;
    }
    for (int k = 0; k < a.length; k++) a[k] = out.get(k);
}