Smooth Sort Intro: Smooth Sort builds up an implicit heap data structure in the array to be sorted, it then sorts the array by continuously extracting the maximum element from that heap. Unlike heapsort, which places the root of the heap and largest element at the beginning of the array before swapping it to the end, smoothsort places the root of the heap at the right, already in its final location. This, however, considerably complicates the algorithm for removing the rightmost element.

Heapsort is an efficient algorithm for sorting, however, consider it a disadvantage of heapsort that it absolutely fails to exploit the circumstances in which the sequence is initially sorted.

Pseudo Code:

Input: An array input of length N.
Output: The array input in sorted order.
// Construct a string of Leonardo heaps from input
// Identify the last index in the array as the back
back = (N − 1)
heapSize = N
while heapSize > 0 do
 // Find the index of the maximum value in the heap
 maximum = HeapMaximum(input)
 // Swap the maximum value with the back of the heap
 back = back − 1
 heapSize = heapSize − 1