Which algorithm does Ruby's sort method use?

Question

When I sort an Array using the native sort method, which algorithm does Ruby use?

Is it data-dependant, i.e., if the data is small it uses X algorithm else it uses Y algorithm?

Is it a stable sort? What is the average time complexity?

AlbertoPL · Accepted Answer · 2009-05-13 02:34:04Z

35

It does natively use quicksort however, which is n log n complexity on average.

answered May 13, 2009 at 2:34

AlbertoPL

11.5k5 gold badges51 silver badges73 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

This also means it is most likely not a stable sort. See the explanations of this at en.wikipedia.org/wiki/Quick_sort

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: As far as I know, also median of three pivot is n^2 in the worse case.

I'm wondering if the word "stupid" is actually a technical word for describing these algorithms

@CarlosMartinez The technical term for "stupid" is "naive".

|