Cartesian Tree Sort

function cartesianSort(arr, stats) {
  const n = arr.length;
  if (n < 2) return;
  const values = [...arr];
  const parent = new Array(n).fill(-1);
  const left = new Array(n).fill(-1);
  const right = new Array(n).fill(-1);
  const stack = [];
  for (let i = 0; i < n; i++) {
    let lastPopped = -1;
    while (stack.length) {
      const top = stack[stack.length - 1];
      compare(top, i);
      if (values[top] <= values[i]) break;
      lastPopped = stack.pop();
    }
    if (stack.length) {
      const top = stack[stack.length - 1];
      right[top] = i;
      parent[i] = top;
    }
    left[i] = lastPopped;
    if (lastPopped !== -1) parent[lastPopped] = i;
    stack.push(i);
  }
  const root = stack[0];
  const frontier = [];
  const compareNodes = (leftNode, rightNode) => {
    if (values[leftNode] !== values[rightNode]) return values[leftNode] - values[rightNode];
    return leftNode - rightNode;
  };
  const siftUp = index => {
    let child = index;
    while (child > 0) {
      const parentIndex = child - 1 >> 1;
      if (compareNodes(frontier[child], frontier[parentIndex]) >= 0) break;
      const temp = frontier[child];
      frontier[child] = frontier[parentIndex];
      frontier[parentIndex] = temp;
      child = parentIndex;
    }
  };
  const siftDown = index => {
    let parentIndex = index;
    while (true) {
      const leftIndex = parentIndex * 2 + 1;
      const rightIndex = leftIndex + 1;
      let smallest = parentIndex;
      if (leftIndex < frontier.length && compareNodes(frontier[leftIndex], frontier[smallest]) < 0) {
        smallest = leftIndex;
      }
      if (rightIndex < frontier.length && compareNodes(frontier[rightIndex], frontier[smallest]) < 0) {
        smallest = rightIndex;
      }
      if (smallest === parentIndex) break;
      const temp = frontier[parentIndex];
      frontier[parentIndex] = frontier[smallest];
      frontier[smallest] = temp;
      parentIndex = smallest;
    }
  };
  const pushNode = node => {
    if (node === -1) return;
    frontier.push(node);
    siftUp(frontier.length - 1);
  };
  const popNode = () => {
    const best = frontier[0];
    const tail = frontier.pop();
    if (frontier.length) {
      frontier[0] = tail;
      siftDown(0);
    }
    return best;
  };
  pushNode(root);
  for (let out = 0; out < n; out++) {
    const node = popNode();
    arr[out] = values[node];
    write(out, arr[out]);
    pushNode(left[node]);
    pushNode(right[node]);
  }
}

def cartesianSort(arr, stats):
    def compareNodes(leftNode, rightNode):
        if (values[leftNode] != values[rightNode]):
            return (values[leftNode] - values[rightNode])
        return (leftNode - rightNode)

    def siftUp(index):
        child = index
        while (child > 0):
            parentIndex = ((child - 1) >> 1)
            if (compareNodes(frontier[child], frontier[parentIndex]) >= 0):
                break
            frontier[child], frontier[parentIndex] = frontier[parentIndex], frontier[child]
            child = parentIndex

    def siftDown(index):
        parentIndex = index
        while True:
            leftIndex = ((parentIndex * 2) + 1)
            rightIndex = (leftIndex + 1)
            smallest = parentIndex
            if ((leftIndex < len(frontier)) and (compareNodes(frontier[leftIndex], frontier[smallest]) < 0)):
                smallest = leftIndex
            if ((rightIndex < len(frontier)) and (compareNodes(frontier[rightIndex], frontier[smallest]) < 0)):
                smallest = rightIndex
            if (smallest == parentIndex):
                break
            frontier[parentIndex], frontier[smallest] = frontier[smallest], frontier[parentIndex]
            parentIndex = smallest

    def pushNode(node):
        if (node == -1):
            return
        frontier.append(node)
        siftUp((len(frontier) - 1))

    def popNode():
        best = frontier[0]
        tail = frontier.pop()
        if len(frontier):
            frontier[0] = tail
            siftDown(0)
        return best

    if (n < 2):
        return
    values = [*arr]
    parent = [-1] * n
    left = [-1] * n
    right = [-1] * n
    stack = []
    for i in range(n):
        lastPopped = -1
        while len(stack):
            top = stack[(len(stack) - 1)]
            compare(top, i)
            if (values[top] <= values[i]):
                break
            lastPopped = stack.pop()
        if len(stack):
            top = stack[(len(stack) - 1)]
            right[top] = i
            parent[i] = top
        left[i] = lastPopped
        if (lastPopped != -1):
            parent[lastPopped] = i
        stack.append(i)
    root = stack[0]
    frontier = []
    pushNode(root)
    for out in range(n):
        node = popNode()
        arr[out] = values[node]
        write(out, arr[out])
        pushNode(left[node])
        pushNode(right[node])

#include <vector>
#include <algorithm>
int compareNodes(int leftNode, int rightNode);
void siftUp(int index);
void siftDown(int index);
void pushNode(int node);
int popNode();

int compareNodes(int leftNode, int rightNode) {
    if((values[leftNode] != values[rightNode])) {
        return (values[leftNode] - values[rightNode]);
    }
    return (leftNode - rightNode);
}

void siftUp(int index) {
    int child = index;
    while((child > 0)) {
        int parentIndex = ((child - 1) >> 1);
        if((compareNodes(frontier[child], frontier[parentIndex]) >= 0)) {
            break;
        }
        std::swap(frontier[child], frontier[parentIndex]);
        child = parentIndex;
    }
}

void siftDown(int index) {
    int parentIndex = index;
    while(1) {
        int leftIndex = ((parentIndex * 2) + 1);
        int rightIndex = (leftIndex + 1);
        int smallest = parentIndex;
        if(((leftIndex < n) && (compareNodes(frontier[leftIndex], frontier[smallest]) < 0))) {
            smallest = leftIndex;
        }
        if(((rightIndex < n) && (compareNodes(frontier[rightIndex], frontier[smallest]) < 0))) {
            smallest = rightIndex;
        }
        if((smallest == parentIndex)) {
            break;
        }
        std::swap(frontier[parentIndex], frontier[smallest]);
        parentIndex = smallest;
    }
}

void pushNode(int node) {
    if((node == -1)) {
        return;
    }
    frontier.push_back(node);
    siftUp((n - 1));
}

int popNode() {
    int best = frontier[0];
    int tail = frontier.back();
    if(n) {
        frontier[0] = tail;
        siftDown(0);
    }
    return best;
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        return;
    }
    std::vector<int> values = {arr};
    std::vector<int> parent(n, -1);
    std::vector<int> left(n, -1);
    std::vector<int> right(n, -1);
    std::vector<int> stack;
    for(int i=0; i<n; i++) {
        int lastPopped = -1;
        while((int)stack.size()) {
            int top = stack[((int)stack.size() - 1)];
            compare(top, i);
            if((values[top] <= values[i])) {
                break;
            }
            lastPopped = stack.back();
        }
        if((int)stack.size()) {
            int top = stack[((int)stack.size() - 1)];
            right[top] = i;
            parent[i] = top;
        }
        left[i] = lastPopped;
        if((lastPopped != -1)) {
            parent[lastPopped] = i;
        }
        stack.push_back(i);
    }
    int root = stack[0];
    std::vector<int> frontier;
    pushNode(root);
    for(int out=0; out<n; out++) {
        int node = popNode();
        arr[out] = values[node];
        write(out, arr[out]);
        pushNode(left[node]);
        pushNode(right[node]);
    }
}

int _listPop(List<int> _l) { int _v = _l[_l.Count - 1]; _l.RemoveAt(_l.Count - 1); return _v; }

int compareNodes(int leftNode, int rightNode) {
    if((values[leftNode] != values[rightNode])) {
        return (values[leftNode] - values[rightNode]);
    }
    return (leftNode - rightNode);
}

void siftUp(int index) {
    int child = index;
    while((child > 0)) {
        int parentIndex = ((child - 1) >> 1);
        if((compareNodes(frontier[child], frontier[parentIndex]) >= 0)) {
            break;
        }
        { int _t = frontier[child]; frontier[child] = frontier[parentIndex]; frontier[parentIndex] = _t; }
        child = parentIndex;
    }
}

void siftDown(int index) {
    int parentIndex = index;
    while(true) {
        int leftIndex = ((parentIndex * 2) + 1);
        int rightIndex = (leftIndex + 1);
        int smallest = parentIndex;
        if(((leftIndex < n) && (compareNodes(frontier[leftIndex], frontier[smallest]) < 0))) {
            smallest = leftIndex;
        }
        if(((rightIndex < n) && (compareNodes(frontier[rightIndex], frontier[smallest]) < 0))) {
            smallest = rightIndex;
        }
        if((smallest == parentIndex)) {
            break;
        }
        { int _t = frontier[parentIndex]; frontier[parentIndex] = frontier[smallest]; frontier[smallest] = _t; }
        parentIndex = smallest;
    }
}

void pushNode(int node) {
    if((node == -1)) {
        return;
    }
    frontier[frontier_len++] = node;
    siftUp((n - 1));
}

int popNode() {
    int best = frontier[0];
    int tail = frontier[--frontier_len];
    if(n) {
        frontier[0] = tail;
        siftDown(0);
    }
    return best;
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        return;
    }
    var values = new List<int> { arr };
    int[] parent = new int[n];
    for(int _i=0;_i<n;_i++) parent[_i]=-1;
    int[] left = new int[n];
    for(int _i=0;_i<n;_i++) left[_i]=-1;
    int[] right = new int[n];
    for(int _i=0;_i<n;_i++) right[_i]=-1;
    var stack = new List<int>();
    for(int i=0; i<n; i++) {
        int lastPopped = -1;
        while(stack.Count) {
            int top = stack[(stack.Count - 1)];
            compare(top, i);
            if((values[top] <= values[i])) {
                break;
            }
            lastPopped = _listPop(stack);
        }
        if(stack.Count) {
            int top = stack[(stack.Count - 1)];
            right[top] = i;
            parent[i] = top;
        }
        left[i] = lastPopped;
        if((lastPopped != -1)) {
            parent[lastPopped] = i;
        }
        stack.Add(i);
    }
    int root = stack[0];
    var frontier = new List<int>();
    pushNode(root);
    for(int out=0; out<n; out++) {
        int node = popNode();
        arr[out] = values[node];
        write(out, arr[out]);
        pushNode(left[node]);
        pushNode(right[node]);
    }
}

#include <stdio.h>
#include <stdlib.h>
int compareNodes(int leftNode, int rightNode);
void siftUp(int index);
void siftDown(int index);
void pushNode(int node);
int popNode();

int compareNodes(int leftNode, int rightNode) {
    if((values[leftNode] != values[rightNode])) {
        return (values[leftNode] - values[rightNode]);
    }
    return (leftNode - rightNode);
}

void siftUp(int index) {
    int child = index;
    while((child > 0)) {
        int parentIndex = ((child - 1) >> 1);
        if((compareNodes(frontier[child], frontier[parentIndex]) >= 0)) {
            break;
        }
        { int _t = frontier[child]; frontier[child] = frontier[parentIndex]; frontier[parentIndex] = _t; }
        child = parentIndex;
    }
}

void siftDown(int index) {
    int parentIndex = index;
    while(1) {
        int leftIndex = ((parentIndex * 2) + 1);
        int rightIndex = (leftIndex + 1);
        int smallest = parentIndex;
        if(((leftIndex < n) && (compareNodes(frontier[leftIndex], frontier[smallest]) < 0))) {
            smallest = leftIndex;
        }
        if(((rightIndex < n) && (compareNodes(frontier[rightIndex], frontier[smallest]) < 0))) {
            smallest = rightIndex;
        }
        if((smallest == parentIndex)) {
            break;
        }
        { int _t = frontier[parentIndex]; frontier[parentIndex] = frontier[smallest]; frontier[smallest] = _t; }
        parentIndex = smallest;
    }
}

void pushNode(int node) {
    if((node == -1)) {
        return;
    }
    frontier[frontier_len++] = node;
    siftUp((n - 1));
}

int popNode() {
    int best = frontier[0];
    int tail = frontier[--frontier_len];
    if(n) {
        frontier[0] = tail;
        siftDown(0);
    }
    return best;
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        return;
    }
    int* values = (int*)malloc(n * sizeof(int)); int values_len = 1;
    values[0] = arr;
    int* parent = (int*)malloc((n) * sizeof(int)); for(int _i=0;_i<n;_i++) parent[_i]=-1;
    int* left = (int*)malloc((n) * sizeof(int)); for(int _i=0;_i<n;_i++) left[_i]=-1;
    int* right = (int*)malloc((n) * sizeof(int)); for(int _i=0;_i<n;_i++) right[_i]=-1;
    int* stack = (int*)malloc(n * sizeof(int)); int stack_len = 0;
    for(int i=0; i<n; i++) {
        int lastPopped = -1;
        while(stack_len) {
            int top = stack[(stack_len - 1)];
            compare(top, i);
            if((values[top] <= values[i])) {
                break;
            }
            lastPopped = stack[--stack_len];
        }
        if(stack_len) {
            int top = stack[(stack_len - 1)];
            right[top] = i;
            parent[i] = top;
        }
        left[i] = lastPopped;
        if((lastPopped != -1)) {
            parent[lastPopped] = i;
        }
        stack[stack_len++] = i;
    }
    int root = stack[0];
    int* frontier = (int*)malloc(n * sizeof(int)); int frontier_len = 0;
    pushNode(root);
    for(int out=0; out<n; out++) {
        int node = popNode();
        arr[out] = values[node];
        write(out, arr[out]);
        pushNode(left[node]);
        pushNode(right[node]);
    }
}