From: Xavier Leroy <Xavier.Leroy@inria.fr>
To: Markus Mottl <mottl@miss.wu-wien.ac.at>, OCAML <caml-list@inria.fr>
Subject: Re: Sort.array easily degenerates
Date: Tue, 9 Mar 1999 11:44:42 +0100 [thread overview]
Message-ID: <19990309114442.07231@pauillac.inria.fr> (raw)
In-Reply-To: <199903060027.BAA03901@miss.wu-wien.ac.at>; from Markus Mottl on Sat, Mar 06, 1999 at 01:27:29AM +0100
> I have played around with the new functions and modules in the new
> OCAML-release. Besides other things I have tested the new function for
> sorting arrays (Sort.array).
> I am not sure where the problem in the implementation is, but the
> "qsort"-function, which is applied in "Sort.array" degenerates easily
> on pre-sorted and/or non-unique data.
The Sort.array implementation is Quicksort with insertion sort for
small partitions, as suggested in Sedgewick. I should know better
than take some code out of an algorithms textbook and expect that it
will work well...
At any rate, any one is welcome to send me a better implementation.
- Xavier Leroy
next prev parent reply other threads:[~1999-03-09 12:34 UTC|newest]
Thread overview: 25+ messages / expand[flat|nested] mbox.gz Atom feed top
1999-03-06 0:27 Markus Mottl
1999-03-09 10:44 ` Xavier Leroy [this message]
1999-03-09 23:03 ` doligez
1999-03-10 13:58 ` Xavier Leroy
1999-03-10 0:28 ` Markus Mottl
[not found] <Xavier.Leroy@inria.fr>
1999-03-05 10:41 ` Objective Caml 2.02 Xavier Leroy
1999-03-05 13:34 ` Camlp4 2.02 Daniel de Rauglaudre
1999-03-05 15:11 ` Objective Caml 2.02 Pierpaolo Bernardi
1999-03-05 19:59 ` doligez
1999-03-11 3:06 ` Upgrade from OCaml 2.01 to OCaml 2.02 made things _slower_! Alexey Nogin
1999-03-11 9:44 ` Xavier Leroy
1999-03-11 23:59 ` Alexey Nogin
1999-03-13 13:40 ` Anton Moscal
1999-03-24 4:20 ` Alexey Nogin
1999-03-26 11:49 ` Anton Moscal
1999-04-06 2:06 ` Alexey Nogin
1999-04-06 7:53 ` Xavier Leroy
1999-03-11 23:42 ` List.filter in Ocaml 2.02 Alexey Nogin
1999-03-12 10:10 ` Wolfram Kahl
1999-03-12 18:18 ` Alexey Nogin
1999-03-13 2:43 ` David Monniaux
1999-03-12 17:01 ` Jean-Francois Monin
1999-03-12 18:41 ` Alexey Nogin
[not found] ` <199903121011.LAA27611@lsun565.lannion.cnet.fr>
1999-03-12 18:37 ` Alexey Nogin
1999-03-15 9:06 ` Jean-Francois Monin
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=19990309114442.07231@pauillac.inria.fr \
--to=xavier.leroy@inria.fr \
--cc=caml-list@inria.fr \
--cc=mottl@miss.wu-wien.ac.at \
/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