From: Alan Cox <alan@lxorguk.ukuu.org.uk>
To: bruce+@andrew.cmu.edu (James R Bruce)
Cc: linux-kernel@vger.kernel.org
Subject: Re: quicksort for linked list
Date: Fri, 9 Mar 2001 11:50:44 +0000 (GMT) [thread overview]
Message-ID: <E14bLPz-0004r4-00@the-village.bc.nu> (raw)
In-Reply-To: <kue=bLNz000142mEtL@andrew.cmu.edu> from "James R Bruce" at Mar 09, 2001 06:09:11 AM
> 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.
Im dubious about anyone doing more than simple bucket sorting for packets.
next prev parent reply other threads:[~2001-03-09 11:48 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2001-03-09 7:38 Manoj Sontakke
2001-03-09 8:36 ` Helge Hafting
2001-03-09 11:52 ` Rogier Wolff
2001-03-09 12:09 ` Thomas Pornin
2001-03-09 18:52 ` Oliver Xymoron
2001-03-10 16:15 ` Jerome Vouillon
2001-03-09 22:29 ` Michal Jaegermann
2001-03-10 18:50 ` Martin Mares
2001-03-10 23:54 ` Michal Jaegermann
2001-03-10 19:09 ` David Wragg
2001-03-12 19:20 ` Jamie Lokier
2001-03-13 6:59 ` James R Bruce
2001-03-09 18:23 ` Oliver Xymoron
2001-03-09 11:09 ` James R Bruce
2001-03-09 11:50 ` Alan Cox [this message]
2001-03-09 18:39 ` Oliver Xymoron
2001-03-09 13:46 ` James Lewis Nance
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=E14bLPz-0004r4-00@the-village.bc.nu \
--to=alan@lxorguk.ukuu.org.uk \
--cc=bruce+@andrew.cmu.edu \
--cc=linux-kernel@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®