Re: [Dev-C++] Sorting Linked Lists and Array Members

[<mol...@se...>]

> ------------ Původní zpráva ------------
> Od: Per Westermark <pw...@ia...>
> Předmět: Re: [Dev-C++] Sorting Linked Lists and Array Members
> Datum: 03.5.2011 11:39:34
> ----------------------------------------
> It is very fast to walk through a linked list once and copy the element
> pointers into an array. That is a linear operation - one extra step for
> every extra element.
> 
> Sorting an array taks n-log-n time which is the best possible for sorting.
> 
> Rebuilding the linked list is one walk through the array, so linear time.
> 
> So using an array is a good sorting method.
> 
> Now try Google and look at bubble sort, insertion sort, merge sort, ...

Merge sort is also n*logn; in fact it's often used on arrays as well. The fact that sorting list in place may be slower than using temporary array is because it needs more cpu instructions to traverse/manipulate a list than an array.