Hi again. The latter half of my email seems to have been forgotten in
the ensuing discussion, so I'll repost. For a linked list of any
non-floating point data, radix sort is almost impossible to beat; it's
iterative, fast (linear time for fixed size integers, worst case), can
be stopped early for partial sorting, and has a pretty simple
implementation.
I've been using essentially the same radix sort implementation I
posted before to sort 1000 item lists 60 times a second in a numerical
application, and it barely shows up in the total time used when
profiling. The other sorts I tried did not fare so well. I would
much rather see this in a kernel modification than any
merge/quick/heap sort implementations I've seen so far for linked
lists. OTOH, this conversation seems to have wandered out of
kernel-space anyway...
- Jim Bruce
(Examples at: http://www.cs.cmu.edu/~jbruce/sort.cc)
10-Mar-2001 Re: quicksort for linked list by David [EMAIL PROTECTED]
> For modern machines, I'm not sure that quicksort on a linked list is
> typically much cheaper than mergesort on a linked list. The
> majority of the potential cost is likely to be in the pointer
> chasing involved in bringing the lists into cache, and that will be
> the same for both. Once the list is in cache, how much pointer
> fiddling you do isn't so important. For lists that don't fit into
> cache, the advantages of mergesort should become even greater if the
> literature on tape and disk sorts applies (though multiway merges
> rather than simple binary merges would be needed to minimize the
> impact of memory latency).
>
> Given this, mergesort might be generally preferable to quicksort for
> linked lists. But I haven't investigated this idea thoroughly.
> (The trick described above for avoiding an explicit stack also works
> for mergesort.)
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
