為什麼 std::list::sort() 中突然切換到自上而下策略？

在Visual Studio 中2015年（VS2015），微軟將std::list::sort()的排序策略從傳統的自下而上的Merge Sort改為自上而下的方法。此變更消除了內部列表數組的使用，並採用迭代器來追蹤原始列表內的排序運行邊界。

更改原因

Stephan T. Lavavej自上而下方法的開發人員指出需要避免記憶體分配和非預設分配器的構造。 VS2015 引入了不再預設可構造和有狀態的分配器，這在使用以前的自下而上方法時帶來了問題。

自上而下方法的實現

頂部-down 方法利用遞歸演算法，將列表遞歸地分成兩半，直到達到列表為空或包含單個元素的基本情況。函數 _Sort 將清單分為三段：左遊、右遊、結束迭代器。合併邏輯是使用 std::list::splice 來移動原始清單內的節點，從而保持異常安全。

效能注意事項

而自頂向下此方法解決了記憶體分配問題，但與原始的自下而上的歸併排序相比，它會帶來性能損失。對於節點分散的大型列表，自上而下的方法會受到快取未命中增加的影響，從而導致執行時間變慢。在這種情況下，將清單移至陣列或向量，對其進行排序，然後從排序後的陣列或向量建立新清單可能會更快。