Quadratic time to sort in a simple case?

[Ivan Kazmenko]

On Tuesday, 23 April 2013 at 17:42:08 UTC, Xinok wrote:

> Choosing a random pivot will always invoke "average" 
> performance where as finding the median of N elements usually 
> achieves better performance on sorted lists. You also have to 
> be careful that equal elements are distributed equally among 
> both partitions, else a list with many elements equal to the 
> pivot will still achieve poor performance. (equal elements 
> would all fall onto one side of the pivot)
>
> Introsort is simply a quick sort which falls back to a heap 
> sort after so many recursions to guarantee O(n log n) 
> performance. I've implemented this using a median of five and 
> it works excellent. This is what I plan to contribute to Phobos.

I like the sound of that!

Regarding my previous post, it's perhaps worth mentioning Go in 
the comparison, it uses QuickSort with median-of-three for small 
sizes and median of medians-of-three for larger sizes [1].  And 
it actually sorts the three medians in median-of-three, which 
sounds like a good thing to do.  They cite "Engineering a Sort 
Function" (1993) by Bentley and McIlroy as inspiration [2].

Ivan Kazmenko.

-----

[1] http://golang.org/src/pkg/sort/sort.go#L104
[2] 
http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/421/09/bentley93engineering.pdf