Cartesian Tree Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Cartesian Tree Sort

An adaptive, heap-based algorithm: build a min-heap structured Cartesian tree in linear time, then sort by repeatedly pulling the minimum element into a priority queue.

How it works

A Cartesian Tree is a binary tree where the parent node has a smaller value than its children (min-heap property), and an in-order traversal of the tree reconstructs the original array. Cartesian Tree Sort operates in two key steps:

1. Tree Construction: Build a Cartesian Tree from the input array in O(n) time. This is achieved using a stack to trace the rightmost path of the tree and make local adjustments.
2. Sorting Phase: Initialize a priority queue (min-heap) with the root of the Cartesian tree. In each step, pop the minimum node from the queue, write its value to the sorted array, and push its left and right children into the priority queue. Repeat until the queue is empty.

Complexity

Interactive visualization

Pseudocode

procedure cartesianTreeSort(A):
  n ← length(A)
  left ← array of size n filled with -1
  right ← array of size n filled with -1
  stack ← empty stack
  
  for i from 0 to n - 1:
    last ← -1
    while stack is not empty and A[top(stack)] > A[i]:
      last ← pop(stack)
    if stack is not empty:
      right[top(stack)] ← i
    if last ≠ -1:
      left[i] ← last
    push(stack, i)
    
  root ← stack[0]
  pq ← new MinPriorityQueue()
  pq.push(root)
  
  sortedIndex ← 0
  while pq is not empty:
    curr ← pq.popMin()
    A[sortedIndex] ← values[curr]
    sortedIndex ← sortedIndex + 1
    if left[curr] ≠ -1:
      pq.push(left[curr])
    if right[curr] ≠ -1:
      pq.push(right[curr])

JavaScript implementation

function cartesianTreeSort(arr) {
  const n = arr.length;
  if (n === 0) return arr;
  
  const left = new Array(n).fill(-1);
  const right = new Array(n).fill(-1);
  const stack = [];
  
  for (let i = 0; i < n; i++) {
    let last = -1;
    while (stack.length > 0 && arr[stack[stack.length - 1]] > arr[i]) {
      last = stack.pop();
    }
    if (stack.length > 0) {
      right[stack[stack.length - 1]] = i;
    }
    if (last !== -1) {
      left[i] = last;
    }
    stack.push(i);
  }
  
  const root = stack[0];
  const pq = [root]; // simple array to act as priority queue
  const sorted = [];
  
  while (pq.length > 0) {
    let minIdx = 0;
    for (let k = 1; k < pq.length; k++) {
      if (arr[pq[k]] < arr[pq[minIdx]]) {
        minIdx = k;
      }
    }
    const curr = pq.splice(minIdx, 1)[0];
    sorted.push(arr[curr]);
    if (left[curr] !== -1) pq.push(left[curr]);
    if (right[curr] !== -1) pq.push(right[curr]);
  }
  
  for (let i = 0; i < n; i++) {
    arr[i] = sorted[i];
  }
  return arr;
}

Pros and cons

When (not) to use it

• Nearly sorted arrays: Extremely fast on data that contains long presorted intervals.
• When memory is constrained: Avoid this algorithm when memory footprint is limited, as the auxiliary parent-child arrays consume significant space.
• Standard tasks: Timsort or standard Quick Sort are generally preferred due to much lower constant factors.