sort linked listW

What is the most efficient way to sort a linked list? In other words,
how is std::list's sort() member function usually implemented?

I was thinking of two approaches:
(1) make an array of pointers from the list nodes, do a quicksort, and
rebuild the list
(2) do an insertion sort, which is simple but has O(n^2) worst-case
complexity

t wrote:google("linked list sort") will find a PDF called "A COMPARATIVE STUDY
OF LINKED LIST SORTING ALGORITHMS", which I guess will comprehensively
answer your question. The linked-list mergesort is the normal best bet.
It certainly isn't necessary to copy the data, or pointers to it, into
another data structure.


Phil.

t wrote:Quicksort is perfectly possible to apply to a linked list. (There
isn't a single step in quicksort which would require random access.)
Likewise merge sort. Heap sort would not be possible.

On Jan 17, 7:08 pm, Juha Nieminen <nos...@thanks.invalidwrote:Yes, but would quicksort be faster. Most efficient
implementations of quicksort that I've seen do use random access
when finding the pivot. Just taking the first (or last) element
will result in very bad performance for some "typical" cases
(initial values almost sorted, for example); the most common
solution seems to be to take the median of the first, last and
middle values, and getting the middle value requires true random
access.

The usual solution I've seen for sorting linked lists is
mergesort, which can be very fast *if* you don't have to
actually copy values (which you don't if you're dealing with
linked nodes).

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34