Cartesian Tree Sort

function cartesianTreeSort(arr) {
  class Node { constructor(v) { this.val=v; this.left=this.right=null; } }
  let root = null;
  const stack = [];
  for (const v of arr) {
    let node = new Node(v), last = null;
    while (stack.length && stack.at(-1).val > v)
      last = stack.pop();
    node.left = last;
    if (stack.length) stack.at(-1).right = node;
    else root = node;
    stack.push(node);
  }
  // In-order traversal of root fills sorted array
}

def cartesian_tree_sort(arr):
    class Node:
        def __init__(self, v):
            self.val, self.left, self.right = v, None, None
    root, stack = None, []
    for v in arr:
        node, last = Node(v), None
        while stack and stack[-1].val > v:
            last = stack.pop()
        node.left = last
        if stack: stack[-1].right = node
        else: root = node
        stack.append(node)
    # In-order traversal fills sorted array

struct CNode { int val; CNode *l = nullptr, *r = nullptr; };
void inOrder(CNode* node, vector<int>& out, int& idx) {
  if (!node) return;
  inOrder(node->l, out, idx);
  out[idx++] = node->val;
  inOrder(node->r, out, idx);
}
void cartesianTreeSort(vector<int>& arr) {
  vector<CNode> nodes(arr.size());
  vector<CNode*> stk;
  CNode* root = nullptr;
  for (int i = 0; i < (int)arr.size(); i++) {
    nodes[i].val = arr[i];
    CNode* last = nullptr;
    while (!stk.empty() && stk.back()->val > arr[i])
      { last = stk.back(); stk.pop_back(); }
    nodes[i].l = last;
    if (!stk.empty()) stk.back()->r = &nodes[i];
    else root = &nodes[i];
    stk.push_back(&nodes[i]);
  }
  int k = 0;
  inOrder(root, arr, k);
}

class CNode { public int Val; public CNode L, R; }
void CartesianTreeSort(int[] arr) {
  CNode root = null;
  var stack = new Stack<CNode>();
  foreach (int v in arr) {
    var node = new CNode { Val = v };
    CNode last = null;
    while (stack.Count > 0 && stack.Peek().Val > v)
      last = stack.Pop();
    node.L = last;
    if (stack.Count > 0) stack.Peek().R = node;
    else root = node;
    stack.Push(node);
  }
  void InOrder(CNode node, int[] outArr, ref int idx) {
    if (node == null) return;
    InOrder(node.L, outArr, ref idx);
    outArr[idx++] = node.Val;
    InOrder(node.R, outArr, ref idx);
  }
  int k = 0;
  InOrder(root, arr, ref k);
}

typedef struct CNode { int val; struct CNode *l, *r; } CNode;
void inOrder(CNode *node, int out[], int *idx) {
  if (!node) return;
  inOrder(node->l, out, idx);
  out[(*idx)++] = node->val;
  inOrder(node->r, out, idx);
}
void cartesianTreeSort(int arr[], int n) {
  CNode nodes[n];
  CNode *stack[n]; int top = 0;
  CNode *root = NULL;
  for (int i = 0; i < n; i++) {
    nodes[i] = (CNode){arr[i], NULL, NULL};
    CNode *last = NULL;
    while (top > 0 && stack[top-1]->val > arr[i])
      last = stack[--top];
    nodes[i].l = last;
    if (top > 0) stack[top-1]->r = &nodes[i];
    else root = &nodes[i];
    stack[top++] = &nodes[i];
  }
  int k = 0;
  inOrder(root, arr, &k);
}