# Cartesian Tree Sort

# 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

```id="k9x3p2"
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:

```id="m3x8q1"
        1
       / \
      2   3
     /     \
    5       6
```

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

```id="p4x2q9"
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
```

```id="z7k3v1"
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
}
```