Объединить сортировку по двойному связанному списку

Question

Считайте, как сортировать связанный список (помимо назначения массива и быстрой сортировки), похоже, что mergesort является одним из лучших методов.

См: Merge Sort a Linked List

текущие вопросы по данной теме не являются специфичными, чтобы погода список является одинарной или двойной связаны между собой.

Моего вопрос:

Есть ли улучшенные методы слияния-сортировочное, что воспользоваться двойными связанными списками? не

(или это так же хорошо, чтобы использовать тот же метод, как один список и назначить previous ссылку только, чтобы убедиться, что список остается в силе)

Answer 1

Насколько мне известно, не существует специальные сберегающие время трюки, возникающие при выполнении объединения в двусвязном списке, которые также не работают в односвязном списке.

Mergesort был первоначально разработан для данных, хранящихся на катушках магнитной ленты, которые можно было читать только в прямом направлении, и большинство стандартных реализаций mergesort только вперед передают элементы. Две основные операции, требуемые mergesort, разделяют входные данные пополам (жесткие как в одно- и двусвязных списках), так и слияния элементов вместе (в обоих случаях они одинаковы). В результате, не делая что-то значительно более умное, чем стандартное слияние, я бы не ожидал, что будут какие-то крупные ускорения.