Rubyのソート方法はどのアルゴリズムを使用していますか？

ネイティブのsortメソッドを使用して配列をソートすると、どのアルゴリズムでRubyが使用されますか？Rubyのソート方法はどのアルゴリズムを使用していますか？

データに依存するかどうか、つまりデータが小さければXアルゴリズムを使用しますか？そうでない場合はYアルゴリズムを使用しますか？

安定した並べ替えですか？平均時間の複雑さは何ですか？

2009-05-13 unj2

Rubyのソートの安定性については、[この質問]（https://stackoverflow.com/questions/15442298/is-sort-in-rubystable）で説明しています。 –

はここを見て：それはネイティブに、しかし、クイックソートを使用しないhttp://www.igvita.com/2009/03/26/ruby-algorithms-sorting-trie-heaps/

nはログインnは平均の複雑されています。

2009-05-13 02:34:04 AlbertoPL

これはまた、安定した並べ替えではない可能性が高いことを意味します。これについての説明はhttp://en.wikipedia.org/wiki/Quick_sort –

を参照してください。特に配列がほぼソートされている場合は、クイックソートの複雑さはn^2になります。それでも、ほとんどの場合、非常に高速です。 – AlbertoPL

配列がほぼソートされている場合、愚かなクイックソートだけがn^2に行きます。 3つのピボット選択の中央値は、私が使用したすべての実装にあります –

答えて