What is the best sorting algorithm for a doubly linked list?
Insertion sort and merge sort appears to the best due to the less overhead compared to the bubble/selection sort.
Would like to know your insights on this.
For linked-lists, the merge-sort algorithm is pretty much the only decent choice. For arrays, things are a lot more subtle and interesting, but not for linked-lists, it's merge-sort that's just the clear winner over any other option (although it could be that insertion-sort is better when the list is very … Read More
Back in the "dark ages", when I needed to sort a linked list, I would put the nodes into an array, then use qsort to sort that, and then rebuild the list from the array. Worked well. Was simple. And it was quite fast. It also met the KISS principle. Read More
IMAO, the best approach to sorting a linked list is not to let it get out of order in the first place. While inserting the nodes in order is slower than pushing them to the head of the list and then sorting, it has the affect of amortizing the sorting … Read More
> Linked lists are elegant, but inefficient to keep sorted. Not if you use a hybrid tree/list, hash/list or a skiplist. :D But those implementations aren't as blindingly simple as a regular linked list, so you don't see them often. Data structures are an exercise in trade-offs. You can have … Read More
**Thomas_25**: rubberman and deceptikon have, indirectly, brought up a good point: is a doubly linked list what you actually need for your purposes, or would an ordered tree structure of some kind (e.g., a priority queue, an AVL tree, a splay tree) serve your needs better? Now, obviously, if this … Read More
I agree that data structures are all about placing the trade-offs where it's most appropriate. When we talk about some kind of sorted container, e.g., something with an interface similar to `std::set`, then there are three fundamental operations: insertion / deletion, in-order traversal, and (range) look-ups. There are basically three … Read More