STL的列表使用哪種排序算法：sort（）？

Question

我有一個隨機整數列表。我想知道列表:: sort（）方法使用哪種算法。例如。在下面的代碼：

list<int> mylist; 

// ..insert a million values 

mylist.sort(); 

編輯：也this more specific question見。

Answer 1

該標準不需要特定算法，只需要它是穩定的，並且它使用大約N lg N比較來完成排序。例如，這允許快速排序的合併排序或鏈接列表版本（與流行的觀點相反，儘管數組最常見的實現是快速排序，但不是不穩定的）。

有了這個條件，簡單的答案是，在大多數當前的標準庫中，std::sort被實現爲一個介紹類（內省類），它基本上是一個跟蹤其遞歸深度的Quicksort，並且將切換到如果Quicksort使用的遞歸太深，則通常較慢但保證O（n log n）複雜度）。儘管如此（儘管在20世紀90年代後期）Introsort是最近發明的。較舊的標準庫通常使用Quicksort。

stable_sort存在是因爲用於分揀陣列狀的容器，最最快排序算法是不穩定的，因此，標準既包括std::sort（快但不一定穩定）和std::stable_sort（穩定的，但往往有些慢）。

但是，這兩種方法通常都需要隨機訪問迭代器，並且會像鏈表一樣工作得很差（如果有的話）。爲了獲得不錯的鏈接列表性能，該標準包含list::sort。然而，對於鏈表而言，並沒有真正的這種折衷 - 實現合併排序非常簡單，這種合併排序的穩定性與其他任何情況一樣穩定和（約）。因此，他們只需要一個要求穩定的sort成員函數。

Answer 2

它完全實現了定義。該標準所說的唯一的事情就是它的複雜性是O（n lg n），而且排序是穩定的。也就是說，在排序後，相等元素的相對順序保證不會改變。

std::list的排序成員函數通常使用某種形式的合併排序來實現，因爲合併排序是穩定的，並且在使用鏈接列表時合併確實非常便宜。

希望幫助:)

Answer 3

雖然是執行/供應商的依賴，但大多數的實現我知道使用內省排序，其最佳&最壞情況複雜度爲O（nlogn）。

參考：http://en.wikipedia.org/wiki/Introsort