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/