Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:110299 Return-Path: Delivered-To: mailing list internals@lists.php.net Received: (qmail 36815 invoked from network); 29 May 2020 12:24:46 -0000 Received: from unknown (HELO php-smtp4.php.net) (45.112.84.5) by pb1.pair.com with SMTP; 29 May 2020 12:24:46 -0000 Received: from php-smtp4.php.net (localhost [127.0.0.1]) by php-smtp4.php.net (Postfix) with ESMTP id 812F91804C9 for ; Fri, 29 May 2020 04:05:41 -0700 (PDT) X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on php-smtp4.php.net X-Spam-Level: X-Spam-Status: No, score=-0.2 required=5.0 tests=BAYES_20,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,HTML_MESSAGE, RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H2,SPF_HELO_NONE,SPF_PASS autolearn=no autolearn_force=no version=3.4.2 X-Spam-ASN: AS15169 209.85.128.0/17 X-Spam-Virus: No X-Envelope-From: Received: from mail-lj1-f169.google.com (mail-lj1-f169.google.com [209.85.208.169]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (P-256) server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by php-smtp4.php.net (Postfix) with ESMTPS for ; Fri, 29 May 2020 04:05:41 -0700 (PDT) Received: by mail-lj1-f169.google.com with SMTP id q2so2054456ljm.10 for ; Fri, 29 May 2020 04:05:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=i5l7Kbl33oferlFP1lXEKgrTl9nIk+YMImnmyysxssU=; b=Dbx7hCVIm094Q4Suc/Y0/0Ul9PdWI4CkpFo5c3xJuiwui48AElaJ/6UTfpVZJGSrHq 1kz4+rvAYTflWyagybHt8TilkX7X3Q3xDFHxm65FwnHTG3lXmGrBsyyBy/OlyZU7FqpM aPKCtNSFcrXJUpcfihdRl8Oa4T+V4gXZskGa8beMhJhFJI+80AxXQf++VBVM7t4uGTVM 4VxiSnO0RaUb0sz1Kg5vXQUABzC3GfbKMC/UZlUCMIH9OiKB/TL+qGiVc7sXYg1eiJY8 /gG8qtxy6BGBZk6sy6D6idE33NUvjEsFr9jBo6qAQLBNIIfEFUsRnd6jKF7flE5zNItX KyCA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=i5l7Kbl33oferlFP1lXEKgrTl9nIk+YMImnmyysxssU=; b=RiOcbhMiK5OliD2flbGahiG3ISYHVtjBsmvYA3aHfOfhRMpLl8F1C/4dY9/ccsfiif tgEwYNVEC6WruqiHtVrZJuo1l/tExBCThGQ0Umlmi3pG7CpszxD1Dze3yEgM2/C+FXUx zDmxl7s6qGY06PJWirtNqZPQQ58zOKN7/m7uB7bX3znUC/YJnnNENmBWS8cSomXX373d HO7+2XfkWnaoKM8btLprIxSzSVvqW9YgGes6lTtn8ftj1+0si6RtSUr2bWNHcOAvaGgq pJ66F0O+6PezVvybp2wh9TO99Y0VhWqsvt4bumcaeD99HXPg0jUZ7tw/xAdKJ8urob+G xHpQ== X-Gm-Message-State: AOAM533Z4mroMrqYS1kICYOFly5AYbqGyM0wmPvlRh5JLypwj4Dy55BJ 6tV4zTSt6iEcmW+EC2Kc3UVrSlxBQSh26M1cFxMAxrI3PFM= X-Google-Smtp-Source: ABdhPJwUsKKtBrtdBBgkq81AtloR5UcmtVFpg+k89xE2oOeQy2PIT3aUixZVnRV+O+fbQjSYTFPJ/Y7oNEF7SBtla/4= X-Received: by 2002:a2e:9081:: with SMTP id l1mr4182157ljg.81.1590750337056; Fri, 29 May 2020 04:05:37 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: Date: Fri, 29 May 2020 13:05:21 +0200 Message-ID: To: PHP internals Content-Type: multipart/alternative; boundary="000000000000c443d105a6c76c89" Subject: Re: [RFC] Make sorting stable From: nikita.ppv@gmail.com (Nikita Popov) --000000000000c443d105a6c76c89 Content-Type: text/plain; charset="UTF-8" On Tue, May 12, 2020 at 4:18 PM Nikita Popov wrote: > Hi internals, > > This was previously discussed in https://externals.io/message/108841, but > I figured it would make sense to create an RFC for this change: > https://wiki.php.net/rfc/stable_sorting > > As before, the implementation approach is to stick with the existing qsort > and use a fallback comparison criterion, which is cheap to implement > internally. The obvious alternative is to use a stable base sort like > Timsort. I gave this a quick try in > https://github.com/php/php-src/pull/5559, and it does better in some > cases (already sorted data) and worse in others (random data). I don't plan > to pursue this direction personally. (It may also be interesting to use > pdqsort as the unstable base, which should make the "already sorted" case > faster.) > If nothing new comes up, I plan to open voting on this RFC soon. Nikita --000000000000c443d105a6c76c89--