Cartesian Tree Adaptive Sort

Cartesian tree adaptive sort builds a Cartesian tree from the input sequence and uses its structure to produce sorted output. The tree encodes both the order of elements and their relative values.

You use it when input has structure that can be exploited through tree shape.

Problem

Given an array ( A ), sort it by:

• constructing a Cartesian tree
• extracting elements in sorted order

A Cartesian tree satisfies:

• heap property on values
• in-order traversal matches the original sequence order

Idea

A Cartesian tree is defined such that:

• the root is the minimum element
• left subtree is built from elements to the left
• right subtree is built from elements to the right

This structure captures both ordering and value hierarchy.

Algorithm

Build Cartesian Tree

build_cartesian_tree(A):
    stack = []
    
    for x in A:
        last = null

        while stack not empty and stack.top.value > x:
            last = stack.pop()

        node = new_node(x)
        node.left = last

        if stack not empty:
            stack.top.right = node

        stack.push(node)

    return bottom_of_stack(stack)

Extract Sorted Order

Use a priority-based traversal (heap-like behavior):

cartesian_tree_sort(root):
    heap = min_heap()
    heap.push(root)

    result = []

    while heap not empty:
        node = heap.pop()
        result.append(node.value)

        if node.left:
            heap.push(node.left)
        if node.right:
            heap.push(node.right)

    return result

Example

Input:

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

Cartesian tree:

        1
       / \
      2   3
     /     \
    5       6

Extracting in priority order yields:

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

Correctness

The Cartesian tree enforces the heap property:

[ \text{parent} \le \text{children} ]

Thus, the root is always the smallest element. Using a min heap over nodes ensures that the next smallest available element is selected. This is equivalent to merging multiple ordered substructures.

Complexity

Space:

[ O(n) ]

Adaptivity

If the input is nearly sorted, the Cartesian tree becomes skewed in a way that reduces restructuring work during construction. This leads to fewer stack operations.

When to Use

Use Cartesian tree adaptive sort when:

• input structure is meaningful
• tree-based representation is already needed
• adaptive behavior is desired

In practice, it is less common than merge-based adaptive sorts but useful in theoretical and specialized contexts.