When I sort an Array using the native sort method, which algorithm does RUBY decide to use? Is it data-dependant (i.e If the data is small it uses X algorithm else uses Y algorithm)? Is it a stable sort? What is the average time complexity?
+4
A:
Look here: http://www.igvita.com/2009/03/26/ruby-algorithms-sorting-trie-heaps/
It does natively use quicksort however, which is n log n complexity on average.
AlbertoPL
2009-05-13 02:34:04
This also means it is most likely not a stable sort. See the explanations of this at http://en.wikipedia.org/wiki/Quick_sort
Matthew Flaschen
2009-05-13 02:39:51
True, especially if the array is almost sorted, then quick sort's complexity becomes n^2. Still, it is extremely fast in most cases.
AlbertoPL
2009-05-13 02:41:58
If the array is almost sorted, only a stupid quicksort goes to n^2. Median of three pivot selection is in all implementattions I've used
Stephan Eggermont
2009-12-13 21:52:12