From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by c5ff346549e7 (Postfix) with ESMTPS id C92A15D6 for ; Sat, 9 Oct 2021 04:05:47 +0000 (UTC) X-IronPort-AV: E=Sophos;i="5.84,326,1620684000"; d="asc'?scan'208";a="532943076" Received: from prod-listesu18.inria.fr (HELO sympa.inria.fr) ([128.93.162.160]) by mail2-relais-roc.national.inria.fr with ESMTP; 09 Oct 2021 06:05:46 +0200 Received: by sympa.inria.fr (Postfix, from userid 20132) id 5DCBAE019E; Sat, 9 Oct 2021 06:05:46 +0200 (CEST) Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id ADFC0E003C for ; Sat, 9 Oct 2021 06:05:43 +0200 (CEST) Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=christophe@raffalli.eu; spf=Pass smtp.mailfrom=christophe@raffalli.eu; spf=None smtp.helo=postmaster@mail.raffalli.eu IronPort-PHdr: =?us-ascii?q?A9a23=3ACUJutRWcxbcUYXrD3s8pT65xe2DV8KwyVTF92vM?= =?us-ascii?q?cY1JmTK2v8tzYMVDF4r011RmVB92duqsP1rWempujcFRI2YyGvnEGfc4EfD4+o?= =?us-ascii?q?uJSoTYdBtWYA1bwNv/gYn9yNs1DUFh44yPzahANS47xaFLIv3K98yMZFAnhOgp?= =?us-ascii?q?pPOT1HZPZg9iq2+yo9JDffRlEiCC5bL9vIxm7rQfcvdQKjIV/Lao81gHHqWZSd?= =?us-ascii?q?eRMwmNoK1OTnxLi6cq14ZVu7Sdete8/+sBZSan1cLg2QrJeDDQ9LmA6/9brugX?= =?us-ascii?q?ZTQuO/XQTTGMbmQdVDgff7RH6WpDxsjbmtud4xSKXM9H6QawyVD+/6apgVR3mh?= =?us-ascii?q?zodNzMh/m/ZitJ+gr9Yrh2uuxNw3pXZYI6JOPdkZK7RYc8WSGhHU81MVyJBGIS?= =?us-ascii?q?8b44XAucfPeZYtYj9p0ASrRu5HQmsBP3gwSJUiHDs06063f4uEQXC3AwhAtkDt?= =?us-ascii?q?2jbrNXvNKcTSuC10K7IzS3Db/xIwjr98pLHch4vof6WWbJwdcvRxVMxGAPYl1i?= =?us-ascii?q?dr5HuMDyJ2OoXqWeb8/ZgWvy1i24hswx8oSWjy8cjh4THmo4Z103I+Cd9zYg7O?= =?us-ascii?q?9G1SE51b9CqHpZftSyXM4V7T98/T210tis3zqALtIOncSYFyJkpyADTZvqaeIa?= =?us-ascii?q?G5RLjUfyeITZ+hH99d7K/hgqy8Ui9yuLnTMW7zFFKri9Dn9LRtX4NzwTe5tWIR?= =?us-ascii?q?/Zy5Eus3SuD2xrX5+1YO0w4i6TWJpA5zrItipYev17PEjH2lUj5lqOaaEsp9+i?= =?us-ascii?q?y5+npfrnroIKXOZVuhQHkKKsun9SyAeQmPQgKWGiW4eG826fi/U39WrlKlOc5k?= =?us-ascii?q?qfXsJ/AIcQboq+5DxVL3YY+8xq/DjGm38oEnXQfMV5Idx2Kg5LtNl3TOvz1Ceu?= =?us-ascii?q?zj06ynDplyf3KJrjhDY/MLnjHnrfhZ7F960tExQUvzdBf/ZNUCqodIPL0Qk/xt?= =?us-ascii?q?MLXAwQjMwOuzebnBs9y1ocaWWKOGKOWLr7SvUeS5u0zO+mMeJMVuDHlJvc5/fH?= =?us-ascii?q?uiHs5lUYZfamoxpsXdGu1Hu9mIkWceXrjmM0NEWYMvgokTezlkkeOUTBJZyX6Y?= =?us-ascii?q?6Vp7Tg+DMeiDJzfboGrmr2ImimhTbNMYWUTIVCWEGz0cJ2EVr82YSycK8tlk3R?= =?us-ascii?q?QXri7SpQ90gmuuSfgwrRpJ+7Q+2sVqMSwh5BO++TPmERqpnRPBMOH3jTVJ4mRt?= =?us-ascii?q?nkBSTE/2KR+50FgmA/rOUdQmfVWG9VX4/IPXxpobPY0LsR/AtH2HBjIcNmATFK?= =?us-ascii?q?nBNi7U2lZcw=3D=3D?= IronPort-HdrOrdr: =?us-ascii?q?A9a23=3Au4w24aiszH4GQju+6HIb5APqInBQXscji2hC?= =?us-ascii?q?6mlwRA09TyX4rbHMoB11726QtN98Yh8dcLO7WJVoP0msl6KdiLN5VdzJYOCBgg?= =?us-ascii?q?qVxepZgbcKrQeMJ8SHzIFg6Zs=3D?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0DgBQCYahph/+laW5BaHgEBCxIMhTtXK?= =?us-ascii?q?BIxhEeJBJlTjH0LAQMBCAUxDgIEAQGHTx4HAQQ0EwECBBUBAQUBAQECAQMDBAG?= =?us-ascii?q?BEBOFaA2CNSKEFR0BAThcAoNkgwYBD6dsgTETboIHAQEGhiiBUwcDBoE6gVOEH?= =?us-ascii?q?QoJQIdzP4FOh1oCgi2CSoJkhVKBBVWSZatqgzKBN4dxgRWTe0UQgSuCGJICkSC?= =?us-ascii?q?iT5NXhTCBdySBWU0mTYJpUBkOjiCDcoEBigEdMjgCBgsBAQMJaSYTiFMBAQ?= X-IPAS-Result: =?us-ascii?q?A0DgBQCYahph/+laW5BaHgEBCxIMhTtXKBIxhEeJBJlTjH0?= =?us-ascii?q?LAQMBCAUxDgIEAQGHTx4HAQQ0EwECBBUBAQUBAQECAQMDBAGBEBOFaA2CNSKEF?= =?us-ascii?q?R0BAThcAoNkgwYBD6dsgTETboIHAQEGhiiBUwcDBoE6gVOEHQoJQIdzP4FOh1o?= =?us-ascii?q?Cgi2CSoJkhVKBBVWSZatqgzKBN4dxgRWTe0UQgSuCGJICkSCiT5NXhTCBdySBW?= =?us-ascii?q?U0mTYJpUBkOjiCDcoEBigEdMjgCBgsBAQMJaSYTiFMBAQ?= X-IronPort-AV: E=Sophos;i="5.84,326,1620684000"; d="asc'?scan'208";a="532943047" X-MGA-submission: =?us-ascii?q?MDFE+CcomCsjhbEqYk5vWRsIqV+1m1f4a2jkff?= =?us-ascii?q?sw1vZWCHkyP2plcT5hFLdjhlnHG2EtwldFsIT+4hUBSE4GreAOY8ZaWd?= =?us-ascii?q?d+8t/e56PHvgsqcGsJiRRkC0MXEC1aJvdhDOmkGQHeEsDFl7WCezmS9W?= =?us-ascii?q?sI9zoC7HTzmSjBdU4Vv8lauA=3D=3D?= Received: from vmi311709.contaboserver.net (HELO mail.raffalli.eu) ([144.91.90.233]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 09 Oct 2021 06:05:42 +0200 Received: from localhost (30.235.254.103.dsl.dyn.mana.pf [103.254.235.30]) by mail.raffalli.eu (Postfix) with ESMTPSA id 4611D640921 for ; Sat, 9 Oct 2021 06:05:37 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=raffalli.eu; s=mail; t=1633752339; bh=VANmukDZugNo1LLfGqVq3dRj42M7Vr87ewhG+nCXcqs=; h=Date:From:To:Subject; b=aHpjDoSe/5MwES8Pg4TW13/nZVgrwxSBUQ/kZgIb6gf0WGYZ2qYPMQzQvNMX7q76j 4HNET7af0vy0Doe699LWa0Tw0pupjsdbkHb5/eaN5VV3pWTxST3D7t1l3qDssrCHCp aSCrQVsfpJRhmMfFOC4U5suThKzaMQJAUprm52YQmtHMaNc9I9FLCIMEe9KT93eA2P FGNhhXPstA1M1BRPVmguGYv6tUq1COxKZ9DagXedznK2ClR6zSu3PQe3DUlnp0NoJX 9eJy0HfBzYx8rIUQPiH8ypbL5SE8w+H2G0w1+hIZmhxZGjxUSPQp6vJdNYbjRoDJB5 FOwqqOkbQLL9g== Date: Fri, 8 Oct 2021 18:05:33 -1000 From: Christophe Raffalli To: caml-list@inria.fr Message-ID: <20211009040533.chu7kqqk27r5wcok@oulala> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="p3u5awvojvyzox3s" Content-Disposition: inline Subject: [Caml-list] O(n ln k) sorting for ocaml on github and a challenge Reply-To: Christophe Raffalli X-Loop: caml-list@inria.fr X-Sequence: 18595 Errors-To: caml-list-owner@inria.fr Precedence: list Precedence: bulk Sender: caml-list-request@inria.fr X-no-archive: yes List-Id: List-Help: List-Subscribe: List-Unsubscribe: List-Post: List-Owner: List-Archive: Archived-At: --p3u5awvojvyzox3s Content-Type: text/plain; charset=utf-8 Content-Disposition: inline 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 --p3u5awvojvyzox3s Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQEzBAABCgAdFiEEJ369adg37nCCF0BCVXIaPfvmsfAFAmFhFQkACgkQVXIaPfvm sfC/HAgArZl32oAOtXJT2lAdM02h65f+tJLCLJZmeSVAHYZNcr+ejLcxOMmPCDxp mfXix7r7hCHtxtryxxBpK6nS0ZRSmmSfAcUPB1tMltJGcpm5BiI58x1ZieaWhYu4 Drn9mT/u4WBOWWaT/JmgKeW/MyOnckqmAf/LME5qO9PsJPmzelszE4PUkTLPajNU 5QnWSatWEgeoG5WTkQP2XPuqx7/UbatdJNLKrwOlDBdi8SxfNI5+FLqOnRUdYmYY dVW7UU8vMAGX4mO8pm2RmpZkdRpL3xlyIWSNIXSveJI3Tv+CabE6r/Ly2l1qHMpO UkTd2I8tUR8VUQvBQk+gGhsKfHbU7w== =uIuo -----END PGP SIGNATURE----- --p3u5awvojvyzox3s--