Leonardo heap was introduced by E. W. Dijkstra in 1981, as an implicit data structure for smoothsort that is a variant of heapsort. Smoothsort is an in-place algorithm which sorts n elements in an array by transforming the input into Leonardo heap using only O(1) auxiliary data. Smoothsort offers average performance of O(n⋅log(n)) and best-case performance of O(n).
Like heapsort, smoothsort has the general characteristic of O(n⋅log(n)) when sorting n elements, but for an input that is initially (nearly) sorted, smoothsort is of order O(n), "with a smooth transition between the two, hence its name"