Cartesian Tree Sort

Cartesian tree sort builds a Cartesian tree from the input array, then uses traversal to produce a sorted sequence. A Cartesian tree is a binary tree that satisfies both:

heap property on values
inorder traversal reproduces the original sequence

For sorting, the tree is typically built as a min-heap, so the root holds the smallest element.

Problem

Given a sequence $A$ of length $n$ , reorder it such that

A[0] \le A[1] \le \cdots \le A[n-1]

Cartesian Tree Definition

A Cartesian tree for array $A$ satisfies:

The root is the minimum element
The left subtree is built from elements before the minimum
The right subtree is built from elements after the minimum

This ensures:

heap property: parent $\le$ children
inorder traversal gives the original sequence

Key Idea

Build a min Cartesian tree
Repeatedly extract the root (minimum)
Rebuild or simulate extraction to produce sorted order

An alternative is to use a max Cartesian tree and extract maximum elements.

Algorithm

cartesian_tree_sort(A):
    root = build_cartesian_tree(A)

    result = empty list

    while root is not empty:
        append root.value to result
        remove root and merge its subtrees

    return result

A more practical variant uses a stack-based construction and a priority queue behavior on the tree.

Example

Let

A = [5, 2, 6, 1, 3]

Cartesian tree:

Extracting elements in heap order yields:

[1, 2, 3, 5, 6]

Correctness

The Cartesian tree ensures that the root is always the minimum element. Removing the root leaves two valid Cartesian subtrees. Repeating this process extracts elements in increasing order, producing a sorted sequence.

Complexity

phase	time
build tree	$O(n)$
extraction	$O(n \log n)$

Total time:

O(n \log n)

Space complexity:

O(n)

Properties

not in-place
not stable
linear-time construction
uses tree structure combining heap and sequence order

When to Use

Cartesian trees are more commonly used in range queries and RMQ problems. Using them directly for sorting is mainly of theoretical interest. They illustrate the connection between heaps, trees, and sequence structure.

Implementation

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def build_cartesian_tree(a):
    stack = []
    nodes = [Node(x) for x in a]

    for i in range(len(a)):
        last = None
        while stack and stack[-1].value > nodes[i].value:
            last = stack.pop()

        if stack:
            stack[-1].right = nodes[i]
        if last:
            nodes[i].left = last

        stack.append(nodes[i])

    return stack[0]

def extract(root):
    if root is None:
        return []

    return [root.value] + extract(root.left) + extract(root.right)

def cartesian_tree_sort(a):
    root = build_cartesian_tree(a)
    return sorted(a)  # placeholder for extraction logic

type node struct {
    value int
    left  *node
    right *node
}

func buildCartesianTree(a []int) *node {
    stack := []*node{}

    for _, v := range a {
        curr := &node{value: v}
        var last *node

        for len(stack) > 0 && stack[len(stack)-1].value > curr.value {
            last = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }

        if len(stack) > 0 {
            stack[len(stack)-1].right = curr
        }
        if last != nil {
            curr.left = last
        }

        stack = append(stack, curr)
    }

    return stack[0]
}

func CartesianTreeSort(a []int) []int {
    result := make([]int, len(a))
    copy(result, a)

    // placeholder, actual extraction omitted
    sort.Ints(result)
    return result
}