Sorting with double-linked lists

It looks like the VS .NET 2003 STL implementation uses a merge sort. You could always quicksort it, but it would require you to write node compare/swap functions. Since I don't know the context under which you are using this doubly-linked list, I cannot say for sure...but if you plan on doing a lot of sorting I would choose another data structure or insert elements into sorted order as you go. I hope this helps.

-Scott

Mergesort is probably the easiest way to deal with sorting a linked list - you don't need to worry about the list length for splitting, because you just take every other element for each list - which for lists, doesn't cost you extra (although it would for arrays). The merging is easy to write as well, and best of all, everything can be done in-place.

That said, the STL provides a lovely double-linked list implementation called std::list, and it provides a member "sort" function. The best code is the (properly tested and well-designed) code that you don't have to write yourself [smile]

The STL also provides a templated free "sort" function for containers, but it cannot be used on lists, because the list iterators are not random-access. This is a Good Thing; the standard ways of sorting array-type containers don't work well on lists, at least not without severe modification to the implementation details. By not providing an operator[], etc. for lists, the STL protects you from writing code that's slower (in the big-O sense) that it looks.

I have implemented these algorithms for sorting a doubly-linked list (Ok, well actually for a doubly-linked ring-list, rather than a double-ended list):

BucketSort, MergeSort, SuperQuickSort (modified to allow O(n) best case), QuickSort, AVLSort, RedBlackSort, AASort, SplaySort, BinaryTreeSort, StrandSort, InsertionSort, DualSelectionSort, SelectionSort, ShakerSort, BubbleSort, OddEvenSort

I would go with BucketSort. It's by far the fastest and is quite easy to implement.

Though if you are using C++, perhaps just use STL's sort function.

Actually, if you can somehow get a good pivot value out of a list in constant time (say, average of the first two and last two items), then you can write QuickSort for a doubly linked list with no extra inefficiency, as it just walks from the top and from the bottom, element by element.

The biggest problem with a list (singly or doubly linked) is that you get a cache miss, and possibly a TLB miss, for each and every element you visit. This makes them perform, at run-time, significantly slower than a vector, unless you insert and remove a LOT in the middle of a fairly large collection. If you have less than 500 bytes of data in the collection, a vector is likely to almost always beat a list. (Also consider a deque, if your items are bigger than 16 bytes or so)