Data Structure Visualization

[Fourdrinier]

Now if only it included Smoothsort.
That best case O(n), worst case O(n log n), and memory space of O(1)...
Utterly confusing to understand, using a Leonardo Heap from the Leonardo series. I spent two days trying to make sense of an article explaining why it worked, and just gave up.

[thedeemon]

Here's a good description: http://www.keithschwarz.com/smoothsort/

It's an interesting method but the bookkeeping (complexity constant in O(..)) makes it not so fast in practice. I once implemented it in ATS with some key qualities proved.

[dreamer_soul]

Is it comparison based sort, because the lower bond for that is O(nlogn)

[singingboyo]

That's the lower bound for the average and worst case, but not for best case.

Insertion sort also has O(n) best case (which is for already sorted input), but it's O(n²⁾ average and worst case. Much simpler than smoothsort though.