From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 76336 invoked by alias); 23 Jul 2018 20:57:52 -0000 Mailing-List: contact libc-help-help@sourceware.org; run by ezmlm Precedence: bulk List-Subscribe: List-Post: List-Help: , Sender: libc-help-owner@sourceware.org Received: (qmail 76321 invoked by uid 89); 23 Jul 2018 20:57:51 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-0.9 required=5.0 tests=BAYES_00,KAM_LAZY_DOMAIN_SECURITY,RCVD_IN_DNSWL_NONE autolearn=no version=3.3.2 spammy=H*r:sk:libc-he, Joshua, joshua X-HELO: mail-qt0-f169.google.com Received: from mail-qt0-f169.google.com (HELO mail-qt0-f169.google.com) (209.85.216.169) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 23 Jul 2018 20:57:50 +0000 Received: by mail-qt0-f169.google.com with SMTP id q12-v6so2085994qtp.6 for ; Mon, 23 Jul 2018 13:57:49 -0700 (PDT) Return-Path: Received: from [192.168.8.100] ([184.151.112.228]) by smtp.gmail.com with ESMTPSA id l44-v6sm9371256qtb.58.2018.07.23.13.57.46 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 23 Jul 2018 13:57:47 -0700 (PDT) Subject: Re: Considering merge optimizations from Timsort in __move_merge_adaptive, __move_merge_adaptive_backward To: Joshua Marshall , Carlos O'Donell , adhemerval.zanella@linaro.org Cc: libc-help@sourceware.org References: <3c1e0790-9e50-f27b-b78d-b9149517b3e6@mtu.edu> From: Carlos O'Donell Message-ID: Date: Mon, 23 Jul 2018 20:57:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-IsSubscribed: yes X-SW-Source: 2018-07/txt/msg00014.txt.bz2 On 07/19/2018 11:48 PM, Joshua Marshall wrote: > As for the actual implementations of std::sort, and std::stable_sort, isn't > introspective sort used and not quick sort + merge sort? In any case, I'm > more interested in the std::stable_sort side of things and am nearly > finished with a Timsort implementation with is parallelizable but doesn't > outperform the current std::stable_sort I think in large part because of > the inplace merging. For that matter, I can't seem to track down what the > actual sort type used for std::stable_sort is. If you are interested in std::stable_sort you must discuss this with the C++ maintainers for the implementation you're using. If it's a GNU Toolchain system then it's likely gcc (libstdc++). You can reach out to them on gcc-help (gcc-help@gcc.gnu.org). Cheers, Carlos.