caml-list - the Caml user's mailing list
 help / Atom feed
* [Caml-list] O(n ln k) sorting for ocaml on github and a challenge
@ 2021-10-09  4:05 Christophe Raffalli
  2021-10-09  8:58 ` Mario Pereira
  2021-10-22  4:44 ` Kazuhiko Sakaguchi
  0 siblings, 2 replies; 6+ messages in thread
From: Christophe Raffalli @ 2021-10-09  4:05 UTC (permalink / raw)
  To: caml-list

[-- Attachment #1: Type: text/plain, Size: 523 bytes --]

Hello,

I just pushed on https://github.com/craff/block_sort.git an old piece of code: a
stable sorting algorithm which is in O(n ln k) where n is the size of the list
and k the number of changes of direction.  It is often much faster than
List.sort, on my tests, never more than 10% slower.  The tests are available on
github.

If people are interested I could provide a version for arrays.

A challenge would be to provide a O(n ln k) sorting on list that is always
faster than List.sort. Any ideas ?

Cheers,
Christophe

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

^ permalink raw reply	[flat|nested] 6+ messages in thread

end of thread, back to index

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-10-09  4:05 [Caml-list] O(n ln k) sorting for ocaml on github and a challenge Christophe Raffalli
2021-10-09  8:58 ` Mario Pereira
2021-10-09 19:59   ` Christophe Raffalli
2021-10-11 11:46     ` Niols
2021-10-11 21:27       ` Mario Pereira
2021-10-22  4:44 ` Kazuhiko Sakaguchi

caml-list - the Caml user's mailing list

Archives are clonable: git clone --mirror https://inbox.ocaml.org/caml-list

AGPL code for this site: git clone https://public-inbox.org/ public-inbox