Cartesian tree sorting

Sign up for FREE 1 month of Kindle and read all our books for free.

Get FREE domain for 1st year and build your brand new site

Reading time: 30 minutes | Coding time: 20 minutes

Cartesian tree sorting, also called Levcopoulos Petersson algorithm is an adaptive sorting algorithm, i.e. it performs much better on a partially sorted data. It needs two data structures: a Cartesian tree and a priority queue. The algorithm here uses min-heap Cartesian tree to give a sorted sequence. We can also use max-heap Cartesian tree but that will give a sorted sequence in non-increasing order.

This algorithm performs better than just using a priority queue/heap because it saves lot of operations used to adjusting a heap done when pooping a top element. It basically maintains a priority queue of candidates, and at each step it removes the smallest element to put at the end of sequence while also performing pre-order traversal on Cartesian tree. Pre-order traversal is used since parent is always smaller than the children in the tree.


1. Construct a Cartesian tree for given sequence.
2. Create a priority queue, initially having only the root of Cartesian tree.
3. Pop the minimum value x from the priority queue
4. Add x to the output sequence
5. Push the left child of x from Cartesian tree into priority queue.
6. Push the right child of x from Cartesian tree into priority queue.
7. If priority queue is not empty, goto step 3.

The Cartesian tree sorting for the sequence {1, 14, 5, 0, 8} will be:



  • Worst case time complexity: Θ(NlogN)
  • Best case time complexity: O(N)
  • Space complexity: O(N)


C++ 11

 * c++ 11 code to construct a Cartesian tree. The method cartesianTreeSort
 * will sort the contents of the array.

#include <iostream>
#include <vector>
#include <queue>

struct Node{
    int value;
    Node *left, *right;
    Node *parent;

        value = 0;
        parent = NULL;
        left = NULL;
        right = NULL;

// Used by priority queue
struct compare{
    bool operator()(Node *left, Node *right){
        return left->value > right->value;

class CartesianTree{
    // last pointer to keep track of last node added
    Node *root, *last;

    Node * findLowestNode(Node *node, int x){
        if(node->value < x)
            return node;
        else if(node->parent != NULL)
            return findLowestNode(node->parent, x);
            return NULL;

    Node * getRoot(){
        return root;

    void addNode(int x){
        Node *new_node = new Node;
        new_node->value = x;
        if(root == NULL){
            last = new_node;
            root = new_node;
        Node *z = findLowestNode(last, x);
        if(z == NULL){
            new_node->left = root;
            root->parent = new_node;
            root = new_node;
            new_node->left = z->right;
            z->right = new_node;
            new_node->parent = z;
        last = new_node;

    CartesianTree(std::vector<int> ar){
        root = NULL;
        last = NULL;
        // Call addNode function for each element of the array
        for(auto x : ar){

    void InorderTraversal(Node *node){
        // To print inorder traversal of the tree
        if(node == NULL)
        std::cout << node->value << ' ';

    // Function to sort and store values in array
    void cartesianTreeSort(std::vector<int> &sorted_ar){
        // Initialize input array
        sorted_ar.assign(0, 0);

        // Initialize priority queue
        std::priority_queue<Node *, std::vector<Node *>, compare> p_queue;
        Node *temp = NULL;
            temp =;

int main(){
    std::vector<int> ar = {1, 14, 5, 0, 8};

    CartesianTree tree(ar);
    std::cout << "Inorder Traversal\n";
    std::cout << '\n';

    std::vector<int> sorted;
    std::cout << "Sorted array is\n";
    for(auto x : sorted)
        std::cout << x << ' ';
    std::cout << '\n';


  • It is possible to quantify how much faster algorithm will run than O(nlogn) using a measurement called oscillation. Practically, the complexity is close to O(nlog(Osc)) where Osc is oscillation.
  • Oscillation is small if the sequence is partially sorted, thus the algorithm performs faster with partially sorted sequences.

References/ Further reading