在雙鏈表上合併排序

Question

閱讀排序鏈表的好方法（除了分配數組和快速排序），它看起來像mergesort是更好的方法之一。

請參見：Merge Sort a Linked List

關於這一主題的當前問題都是非特異性的，因爲天氣的列表是單或雙掛鉤。

我的問題是：

合併排序是利用雙鏈表中是否有改善的方法？

（或者是它一樣好使用相同的方法作爲單鏈表和分配previous鏈接只是爲了確保名單仍然有效）

Answer 1

據我所知，沒有在雙鏈表上進行mergesort時出現的特殊節省時間的技巧，這些技巧並不適用於單鏈表。

Mergesort最初是爲存儲在磁帶捲上的數據而開發的，只能在向前的方向讀取數據，並且大多數mergesort的標準實現只是向前傳遞元素。 mergesort需要的兩個主要操作是將輸入分成兩部分（在單向鏈接和雙向鏈接列表中都很難）並將元素合併（在兩種情況下基本相同）。因此，如果沒有比標準合併更聰明的做法，我不會期望有任何重大的加速。