Cartesian Tree Sort Intro: A cartesian tree sort is a form of selection sort, an algorithm which finds the elements of the output sequence in their sorted order, using data structures to speed up how it finds every element. It builds a Cartesian tree on the input, a tree in which the parent of each value is the larger of the two nearest smaller values on either side of it. It maintains a binary heap of active values, initially just the root of the Cartesian tree. And then it repeatedly moves the smallest element of the heap to the output list, replacing it in the heap by its children in the Cartesian tree.

 

Cartesian Tree Sort Explanation:

Construct a Cartesian tree for the input sequence

Initialize a priority queue, initially containing only the tree root

While the priority queue is non-empty:
  • Find and remove the minimum value x in the priority queue
  • Add x to the output sequence
  • Add the Cartesian tree children of x to the priority queue