Программа Javascript для сортировки слиянием для двусвязного списка

Для заданного двусвязного списка напишите функцию для сортировки двусвязного списка в возрастающем порядке с использованием сортировки слиянием.
Например, следующий двусвязный список следует изменить на 24810.

Сортировка слиянием для односвязного списка уже обсуждалась. Важным изменением здесь является изменение предыдущих указателей также при объединении двух списков.

Ниже приведена реализация сортировки слиянием для двусвязного списка.

Выход:

Linked List after sorting
Forward Traversal using next pointer
3 4 5 10 20 30
Backward Traversal using prev pointer
30 20 10 5 4 3

Временная сложность: временная сложность приведенной выше реализации такая же, как временная сложность MergeSort для массивов. Это занимает Θ(nLogn) времени.

Космическая сложность: O(1). Мы используем только постоянное количество дополнительного пространства.
Вам также может понравиться QuickSort для двусвязного списка.
Пожалуйста, обратитесь к полной статье о сортировке слиянием для двусвязного списка для получения более подробной информации!