Cartesian tree sorting

algorithm
sorting-algorithms
cartesian-tree
queue
priority-queue
(Team) #1

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/
0 Likes