From: Thomas Pornin <Thomas.Pornin@ens.fr>
To: R.E.Wolff@bitwizard.nl
Cc: linux-kernel@vger.kernel.org
Subject: Re: quicksort for linked list
Date: Fri, 9 Mar 2001 13:09:02 +0100 [thread overview]
Message-ID: <20010309130902.A24249@bolet.ens.fr> (raw)
In-Reply-To: <200103091152.MAA31645@cave.bitwizard.nl>
In article <200103091152.MAA31645@cave.bitwizard.nl> you write:
> Quicksort however is an algorithm that is recursive. This means that
> it can use unbounded amounts of stack -> This is not for the kernel.
Maybe a heapsort, then. It is guaranteed O(n*log n), even for worst
case, and non-recursive. Yet it implies a significantly larger amount of
comparisons than quicksort (about twice, I think).
Insertion sort will be better anyway for small sets of data (for 5 or
less elements).
--Thomas Pornin
next prev parent reply other threads:[~2001-03-09 12:09 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 [this message]
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
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=20010309130902.A24249@bolet.ens.fr \
--to=thomas.pornin@ens.fr \
--cc=R.E.Wolff@bitwizard.nl \
--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®