**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.

**Read this article to understand Cartesian tree sorting in depth**

**Have a doubt or thought? Join the discussion now**

This is a companion discussion topic for the original entry at http://iq.opengenus.org/cartesian-tree-sorting/