Smoothsort
Sorting algorithm
>
In computer science, smoothsort is a comparison-based sorting algorithm. A variant of heapsort, it was invented and published by Edsger Dijkstra in 1981. Like heapsort, smoothsort is an in-place algorithm with an upper bound of O(n log n)... Wikipedia
Worst-case complexity: n*log(n)
Average complexity: n*log(n)
Best complexity: n
Average performance: O(n log n)
Data structure: Array
Worst-case space complexity: O(n) total, O(1) auxiliary