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 BDFBC5D6 for ; Sat, 9 Oct 2021 08:58:33 +0000 (UTC) X-IronPort-AV: E=Sophos;i="5.84,326,1620684000"; d="scan'208,217";a="532964582" 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 10:58:32 +0200 Received: by sympa.inria.fr (Postfix, from userid 20132) id 51D9FE00CF; Sat, 9 Oct 2021 10:58:32 +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 A2706E003C for ; Sat, 9 Oct 2021 10:58:27 +0200 (CEST) Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=mjp.pereira@fct.unl.pt; spf=Pass smtp.mailfrom=mjp.pereira@fct.unl.pt; spf=None smtp.helo=postmaster@mail-il1-f181.google.com IronPort-PHdr: =?us-ascii?q?A9a23=3AmaWcSBcdZZQi600e+AKO2NyxlGM+IN7LVj580XL?= =?us-ascii?q?Ho4xHfqnrxZn+JkuXvawr0AWRG9SCoK8bw8Pt8InYEVQa5piAtH1QOLdtbDQiz?= =?us-ascii?q?fssogo7HcSeAlf6JvO5JwYzHcBFSUM3tyrjaRsdF8nxfUDdrWOv5jAOBBr/KRB?= =?us-ascii?q?1JuPoEYLOksi7ze+/94PPbwlSgDexfLx+IRW0oA7MqsQYnIxuJ7orxBDUuHVIY?= =?us-ascii?q?eNWxW1pJVKXgRnx49q78YBg/SpNpf8v7tZMXqrmcas2S7xYFykmPHsu5ML3rxn?= =?us-ascii?q?DTBCA6WUaX24LjxdHGQnF7BX9Xpfsriv3s/d21SeGMcHqS70/RC+v5Ll3RhD2l?= =?us-ascii?q?CgHNiY58GDJhcx2kKJbuw+qqxhmz4LJfI2ZKP9yc6XAdt0YWGVBRN5cWCNPAoy?= =?us-ascii?q?+b4UBAekPM/tGoYbhvFYBtweyCBO2Ce/z1jNFhHn71rA63eQ7FgHG2RQtEdUUv?= =?us-ascii?q?3TOrdX1M7oZX/qrw6nS0zrDbulW1i3g44XPdxAho+mMUahoccXP00kgCQLFjk+?= =?us-ascii?q?KpoH+MTOayvgNv3KG7+pmUeKjkXYnqx1orzWp28wjhZXHiJgPxVDY6SV23pw1J?= =?us-ascii?q?dugRUN5f9KpEJRdui+aOoZqQs0vQn1ktTs+x7EbvZO2ciYExpsoyhPedvGKfYa?= =?us-ascii?q?F7g/tWuieIzp0mHJodb2iixus8kWtzPD3WMez0FZPtCVFk9/Mu2gC1xzS9siHS?= =?us-ascii?q?uZ98Vy71TmT0ADT7/lIIVw1lareMJ4hxaQwloYJvUTGGi/7nlj9gqyOdkg85OS?= =?us-ascii?q?k9+Dqbq/lq5KcLYN4lwDzP6U0lsCiAuk0Lw4DVHWB9+umzr3s50j5Ta1KjvIol?= =?us-ascii?q?qnZt4jXJcEBqa64Bw9Zy4cj6xKiAzu/3tQUgHoKIE9fdBKIiIjpPF7OIPTmAvu?= =?us-ascii?q?ln1uslzJry+jHPr3nHJrNMmDOnKn9cbt58UJRywo+wcpC659VC7wNOu//V0zsu?= =?us-ascii?q?NDACx82KQ20w+LpCNVn0YMeXHqCAqqbMKPKq1OI/vwgI/OSa48UojbyMeMo5/D?= =?us-ascii?q?ygn8lg1MdYK+p3Z8NZHCgAvRqO1+Zbmb0gtcdDWcKuRIzQ/Dwh12HVT5ffnKyX?= =?us-ascii?q?6Mn5jEnE4+mFofCRoW1gLObxiu7H5tWZnpHCl+WC3voeZ+ECL8wb3e5ItVgiSA?= =?us-ascii?q?DTbisA7Uo2x+nsAv7g+5sLvDV4TEfrZLu/MJ86ePakRUzszFpWZezyWaIGkR9h?= =?us-ascii?q?GIPDwc7xq1+u0U1nlKBye5gjuZVFMZaz/1CTkEnM5qa1/AsWIO6YR7IYtrcEAX?= =?us-ascii?q?ued6hGzxkC4tpm7fmhm5zEMnkkxbHmTK2Ued9f1OjCpcotL/a2z7pO5Qko54n/?= =?us-ascii?q?Kwojl1jQ88WcGP/1vc5+A/UCIrE1U6ekvTyHZk=3D?= IronPort-HdrOrdr: =?us-ascii?q?A9a23=3ADF3zcqn9g2zMZrhTJRukcCzES/jpDfL93DAb?= =?us-ascii?q?v31ZSRFFG/Fw8Pre4MjztCWE9Qr5PUtKpTnuAtj+fZqiz+8Q3WB8B8baYOCkgh?= =?us-ascii?q?rMEGga1/qA/9S4IVydygc/79YHT0EdMrPN5DFB5K6R3ODSKada/DDoytHRuQ/u?= =?us-ascii?q?pE0BcehCUcBdB/QTMGqm+loffml77OICe6Z1zKF81l2dkN8sH76GOkU=3D?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0B7BQCYahphf7WmVdFaHgEBCxIMghuDI?= =?us-ascii?q?FY7MYRHgR6OK54QgXsLAQMBDTUMBAEBhGECgmsCHQcBBDYEDQECBBUBAQUBAQE?= =?us-ascii?q?CAQMDBAETAQENCxAIOCaFaA2CNSkBg1oKAgEDEhEdAQE3AQ8LAwEHNwICIhIBB?= =?us-ascii?q?QEcBjWCTwGDBw+aeYEEPYsygQwlE26CBwEBBoYogVoDBhKBKIcLAQGGZieCKYF?= =?us-ascii?q?Lgm8+gksXAoINgmqCZIVSwCkHgyuKPZQVK4NToyKiT5h3ECOBVwuBbzMaczEGg?= =?us-ascii?q?jJQGQ6OIINyhWGEfkMvOAIGAQoBAQMJiXUBAQ?= X-IPAS-Result: =?us-ascii?q?A0B7BQCYahphf7WmVdFaHgEBCxIMghuDIFY7MYRHgR6OK54?= =?us-ascii?q?QgXsLAQMBDTUMBAEBhGECgmsCHQcBBDYEDQECBBUBAQUBAQECAQMDBAETAQENC?= =?us-ascii?q?xAIOCaFaA2CNSkBg1oKAgEDEhEdAQE3AQ8LAwEHNwICIhIBBQEcBjWCTwGDBw+?= =?us-ascii?q?aeYEEPYsygQwlE26CBwEBBoYogVoDBhKBKIcLAQGGZieCKYFLgm8+gksXAoINg?= =?us-ascii?q?mqCZIVSwCkHgyuKPZQVK4NToyKiT5h3ECOBVwuBbzMaczEGgjJQGQ6OIINyhWG?= =?us-ascii?q?EfkMvOAIGAQoBAQMJiXUBAQ?= X-IronPort-AV: E=Sophos;i="5.84,326,1620684000"; d="scan'208,217";a="532964551" X-MGA-submission: =?us-ascii?q?MDFy5iGKhaj8rZbsqIYzL/Jz11IjPdWzOPLzGa?= =?us-ascii?q?mgaZw9VfuW5NU/oIB+TmSfAd66ZRH5ArG0nZvvsm7xiAW64bObgUxoog?= =?us-ascii?q?b5zTmjnqOC8nRQrCnYGZ3VQ0zQLfTaTh7rKbm644855LgMwBM4+7lakY?= =?us-ascii?q?ka46zr/4QKwni4CNPEmgEWeQ=3D=3D?= Received: from mail-il1-f181.google.com ([209.85.166.181]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/AES256-GCM-SHA384; 09 Oct 2021 10:58:26 +0200 Received: by mail-il1-f181.google.com with SMTP id k13so12414088ilo.7 for ; Sat, 09 Oct 2021 01:58:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fct.unl.pt; s=googlefct; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=Nof8TsFwrvPZvVIE2w2MZ+yiH0J4xE3o8meKaiPjOuM=; b=Zpcxrf+rzxQLurz7P473DgU/yDFs1LNr1Dg2MvBREgy33WNE3lgInRFoNsX1owNGjN SQ+zzbN8Ss/GZHIGwwH88WGfTKjkRRL+CwOvxrtATWg5d50d0lloiLEpm45uxS2v3Jos MQxwmkF9Uig8EsiB9GbGRaFCbotvor2A1LgMzbwBbDAKMM/YQyLAl1ShwEHkgNL0f722 XSaC8OxlH8V19eh6wGhN08gkrQ3Gg2DZ5i96zu9gNl2botdS+cnhOhyhaoKhiXdZLvBj yh0/OO25es2VuU8Bljw3DynqWKT4egkWvfEm4VkTDP6UKQYe4LuEnNVobjRHiLqAf78B QRNQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=Nof8TsFwrvPZvVIE2w2MZ+yiH0J4xE3o8meKaiPjOuM=; b=e+0tFSGNIND20igAK97mKi3Kbpauby0QBy+7R7EdYguPRTPBCLutfrPsjcpK4KfTqG RJI2Z+2JcbpRwS+1quRkkSW501jK1EcTYFErs7oesoyAtWrCJzxKgIZIQfJsN+v85xHs f13ngTOm3V1tmVaD8uhqQ+z8cvbFhHlJ+2QezUMFNVqxQgxKQ6/KGrxqQDzwlrvBq47D v2O0Zf57FUkEqLtG1Fm8Rlf3Nn0Q37sbPy0FAIr56SNMxq00aUwLeEVCckIWpsdt0pIj MiCa7tHIb8ta+VWEXD+qDIuSi4FE3TC8kfFXJ/4DnH7JO8G/B5rsTGkBdvETwxIcCHY/ AfYQ== X-Gm-Message-State: AOAM532uIn+E10Iqg6IRPS4yihwgISvnJTiChIs8Hkr200JJBsHkDCWL lrvTfI94wEBtBo5+LhN0yUwsqNciaWak34FmRWL4LXh+oeE= X-Google-Smtp-Source: ABdhPJyUdOwUju3OFloAj0vA5g2Qsjd+UvoD8hX71AIo6LeHtcG/orAnnGouvEp7UoqL5WDpbyKONrWYT8GNs4XpC+g= X-Received: by 2002:a92:d847:: with SMTP id h7mr328005ilq.130.1633769904500; Sat, 09 Oct 2021 01:58:24 -0700 (PDT) MIME-Version: 1.0 References: <20211009040533.chu7kqqk27r5wcok@oulala> In-Reply-To: <20211009040533.chu7kqqk27r5wcok@oulala> From: Mario Pereira Date: Sat, 9 Oct 2021 09:58:12 +0100 Message-ID: To: Christophe Raffalli Cc: caml-list@inria.fr Content-Type: multipart/alternative; boundary="000000000000cd87fa05cde7b2a8" Subject: Re: [Caml-list] O(n ln k) sorting for ocaml on github and a challenge Reply-To: Mario Pereira X-Loop: caml-list@inria.fr X-Sequence: 18596 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: --000000000000cd87fa05cde7b2a8 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Christophe, Your implementation reminds me very much of TimSort (for an OCaml implementation, see for instance https://github.com/LesBoloss-es/sorting/blob/master/src/list/timsort.ml). This is also a stable algorithm. Was TimSort an inspiration? Cheers -- M=C3=A1rio --000000000000cd87fa05cde7b2a8 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Christophe,

Your implementation reminds me very much of TimSort (for an O= Caml implementation, see for instance=C2=A0https://github.com/LesB= oloss-es/sorting/blob/master/src/list/timsort.ml). This is also a stabl= e algorithm.

Was TimSort= an inspiration?

Cheers<= /div>
--
M=C3=A1rio
--000000000000cd87fa05cde7b2a8--