From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS4713 221.184.0.0/13 X-Spam-Status: No, score=-2.7 required=3.0 tests=BAYES_00,DKIM_ADSP_CUSTOM_MED, FORGED_GMAIL_RCVD,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS shortcircuit=no autolearn=no autolearn_force=no version=3.4.2 Received: from neon.ruby-lang.org (neon.ruby-lang.org [221.186.184.75]) by dcvr.yhbt.net (Postfix) with ESMTP id C6A1B1F454 for ; Thu, 7 Nov 2019 03:58:18 +0000 (UTC) Received: from neon.ruby-lang.org (localhost [IPv6:::1]) by neon.ruby-lang.org (Postfix) with ESMTP id A7A7E1209EE; Thu, 7 Nov 2019 12:58:09 +0900 (JST) Received: from o1678948x4.outbound-mail.sendgrid.net (o1678948x4.outbound-mail.sendgrid.net [167.89.48.4]) by neon.ruby-lang.org (Postfix) with ESMTPS id 776091209DD for ; Thu, 7 Nov 2019 12:58:07 +0900 (JST) Received: by filter0082p3mdw1.sendgrid.net with SMTP id filter0082p3mdw1-5618-5DC39655-32 2019-11-07 03:58:13.800083952 +0000 UTC m=+119906.027460496 Received: from herokuapp.com (unknown [34.230.5.86]) by ismtpd0066p1mdw1.sendgrid.net (SG) with ESMTP id sajhxx8zSn-myosduxvahw for ; Thu, 07 Nov 2019 03:58:13.742 +0000 (UTC) Date: Thu, 07 Nov 2019 03:58:13 +0000 (UTC) From: rogerpack2005@gmail.com Message-ID: References: Mime-Version: 1.0 X-Redmine-MailingListIntegration-Message-Ids: 71361 X-Redmine-Project: ruby-trunk X-Redmine-Issue-Id: 1089 X-Redmine-Issue-Author: murphy X-Redmine-Issue-Assignee: matz X-Redmine-Sender: rogerdpack X-Mailer: Redmine X-Redmine-Host: bugs.ruby-lang.org X-Redmine-Site: Ruby Issue Tracking System X-Auto-Response-Suppress: All Auto-Submitted: auto-generated X-SG-EID: =?us-ascii?Q?v8hSzEGfbrk44MJiDqVStTpSC1xoh57IEcMaJF+wqMxcyrWtSFLycgw9zxW03s?= =?us-ascii?Q?G=2FMkuh5gTTKfj3jACL8xZsyR3BDvIWUlhitKfUv?= =?us-ascii?Q?eeddYKAXc5xf1VHYOVvFA2ZnpYz4NjSkhRp1fxH?= =?us-ascii?Q?D65tGXCn0BVF29MA9w2Pi3E4fKnR4lWer27=2F2sR?= =?us-ascii?Q?tTMQLraBJ3Qbp6u8uREvI4tOW6Ky72FnVug=3D=3D?= To: ruby-core@ruby-lang.org X-ML-Name: ruby-core X-Mail-Count: 95736 Subject: [ruby-core:95736] [Ruby master Feature#1089] Stable sorting for sort and sort_by X-BeenThere: ruby-core@ruby-lang.org X-Mailman-Version: 2.1.15 Precedence: list Reply-To: Ruby developers List-Id: Ruby developers List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: ruby-core-bounces@ruby-lang.org Sender: "ruby-core" Issue #1089 has been updated by rogerdpack (Roger Pack). It's sad that #sort on linux is "mostly stable" but on OS X is unstable [1]. It's confusing, unfortunately. Since almost always when I do a "sort_by(&:x).sort_by(&:y)" I am looking for a stable sort. And that's exactly the reason that java gives for defaulting to a stable sort if it's dealing with objects [2]. Might be nice to add a stable sort option, here's a fork with a timsort: https://github.com/ruby/ruby/compare/master...phluid61:timsort benchmarks are here: https://www.ruby-forum.com/t/timsort-in-ruby/235311/7 it's slightly slower than the unstable sort. Anyway it would be nice to at least have it around in core, and, in my mind, be the default for at least sort_by but that's up to discretion... [1] https://github.com/crystal-lang/crystal/issues/2350#issuecomment-550188746 [2] https://stackoverflow.com/a/15154287/32453 "Stability is a big deal when sorting arbitrary objects. For example, suppose you have objects representing email messages, and you sort them first by date, then by sender. You expect them to be sorted by date within each sender, but that will only be true if the sort is stable." ---------------------------------------- Feature #1089: Stable sorting for sort and sort_by https://bugs.ruby-lang.org/issues/1089#change-82555 * Author: murphy (Kornelius Kalnbach) * Status: Rejected * Priority: Normal * Assignee: matz (Yukihiro Matsumoto) * Target version: ---------------------------------------- =begin I'd like to have stable sorting in Ruby. Stable sorting means that if two items are ==, they will retain their order in the list after sorting. In other words, stable sort does never switch two equal items. In Ruby 1.9.1, you'd have to use something like enum.sort_by.with_index { |a, i| [a, i] } to achieve a stable sort in Ruby. It would also be nice to minimize the number of comparisons, since method calling is expensive in Ruby. Python is using a highly optimized implementation of a variant of merge sort, which is stable and uses very few comparisons (called Timsort after Tim Peters); maybe Ruby can adopt it for sort and sort_by: http://svn.python.org/projects/python/trunk/Objects/listsort.txt Introducing stable sorting would not be a problem for old code because the order of equal items after sorting is currently not specified. =end -- https://bugs.ruby-lang.org/