On Fri, 9 Mar 2001, Alan Cox wrote:
> > Quicksort works just fine on a linked list, as long as you broaden
> > your view beyond the common array-based implementations. See
> > "http://www.cs.cmu.edu/~jbruce/sort.cc" for an example, although I
> > would recommend using a radix sort for linked lists in most situations
> > (sorry for the C++, but it was handy...).
>
> In a network environment however its not so good. Quicksort has an N^2
> worst case and the input is controlled by a potential enemy.
It's not too hard to patch that up, eg quickersort. N^2 isn't too bad for
short queues anyway especially considering the complexity of the
alternatives.
> Im dubious about anyone doing more than simple bucket sorting for packets.
Assume you mean sorting into hash buckets as opposed to "count the number
of occurrences of each type of element in a narrow range, discarding the
actual element". Most hashes are subvertible too and probably don't fair
any better than N^2.
-- "Love the dolphins," she advised him. "Write by W.A.S.T.E.."- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Thu Mar 15 2001 - 21:00:10 EST