Cartesian tree sorting

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