Reading up on the good ways to sort a linked list (besides assigning an array and quick-sorting), it looks like mergesort is one of the better methods.
The current questions on this topic are non-specific as to weather the list is single or double linked.
My question is:
Is there improved methods of merge-sorting that take advantage of double linked lists?
(or is it just as good to use the same method as a single linked list and assign the previous link just to ensure the list remains valid)
To the best of my knowledge, there are no special time-saving tricks that arise when doing mergesort on a doubly-linked list that don't also work on a singly-linked list.
Mergesort was originally developed for data stored on reels of magnetic tape that could only be read in a forwards direction, and most standard implementations of mergesort only do forwards passes over the elements. The two major operations required by mergesort are splitting the input in half (hard in both singly- and doubly-linked lists) and merging elements back together (basically the same in both cases). As a result, without doing something substantially more clever than a standard mergesort, I would not expect there to be any major speedups.
