Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

"When the going gets weird, the weird turn pro..." -- Hunter S. Thompson


devel / comp.lang.python / Re: new sorting algorithm

SubjectAuthor
* Re: new sorting algorithmChris Angelico
`* Re: new sorting algorithmcharles hottel
 `- Re: new sorting algorithmMats Wichmann

1
Re: new sorting algorithm

<mailman.289.1651448745.20749.python-list@python.org>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=18100&group=comp.lang.python#18100

 copy link   Newsgroups: comp.lang.python
Path: i2pn2.org!rocksolid2!i2pn.org!news.swapon.de!fu-berlin.de!uni-berlin.de!not-for-mail
From: ros...@gmail.com (Chris Angelico)
Newsgroups: comp.lang.python
Subject: Re: new sorting algorithm
Date: Mon, 2 May 2022 09:45:32 +1000
Lines: 54
Message-ID: <mailman.289.1651448745.20749.python-list@python.org>
References: <CADs8Xt5LE4f5ayJ5n94+KKyR3bGQ13dk-Tr_u7XhFaEuwxpVOg@mail.gmail.com>
<CAPTjJmq3VgD+OyiL4W=m2Bo0BJwHaYY69a=mAPJx5vMnfBdHFg@mail.gmail.com>
<CAGGBd_p9iNwiAe87E1x759Oo659HTAO9Frs7L8fzpTq9+J0Rmg@mail.gmail.com>
<CAPTjJmpZEQSgzL2b50FK+mK7dNJgJwd2YteqjxyxWZi_o4UUJQ@mail.gmail.com>
<CAGGBd_otruOBmwWv5yhhRZB=BJ547pitiTCTODXwV0Km8OnMRw@mail.gmail.com>
<CAPTjJmotvBiPTQC8bpYUS+y3Avrt1gyr5y5O6WCmVHNyWJiEHA@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
X-Trace: news.uni-berlin.de CARl39RrjRPgy8pume0PVQb0F1Iw3DmoIZXTi4s/0q1A==
Return-Path: <rosuav@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
Authentication-Results: mail.python.org; dkim=pass
reason="2048-bit key; unprotected key"
header.d=gmail.com header.i=@gmail.com header.b=VRx8d4Df;
dkim-adsp=pass; dkim-atps=neutral
X-Spam-Status: OK 0.001
X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; '2022': 0.05; "python's":
0.05; 'real-world': 0.07; 'sun,': 0.07; 'angelico': 0.09;
'check,': 0.09; 'dan': 0.09; 'fact,': 0.09; 'manages': 0.09;
'tricks': 0.09; 'log': 0.12; 'that.': 0.15; '(plus,': 0.16;
'algorithms,': 0.16; 'append': 0.16; 'bulk': 0.16; 'chrisa': 0.16;
'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16;
'handful': 0.16; 'hardly': 0.16; 'partitioning': 0.16; 'purely':
0.16; 'received:209.85.221.54': 0.16; 'received:mail-
wr1-f54.google.com': 0.16; 'sort,': 0.16; 'sorted': 0.16;
'wrote:': 0.16; 'to:addr:python-list': 0.20; 'list,': 0.24; "i'd":
0.24; 'cannot': 0.25; "isn't": 0.27; 'chris': 0.28; 'fact': 0.28;
'sense': 0.28; 'it,': 0.29; 'seem': 0.31; 'think': 0.32; 'cool':
0.32; 'message-id:@mail.gmail.com': 0.32; 'develop': 0.32; 'but':
0.32; "i'm": 0.33; 'header:In-Reply-To:1': 0.34;
'received:google.com': 0.34; 'item': 0.35; 'close': 0.35;
'from:addr:gmail.com': 0.35; 'mon,': 0.36; 'using': 0.37; "it's":
0.37; 'received:209.85': 0.37; 'hard': 0.37; 'could': 0.38;
'received:209': 0.39; 'quite': 0.39; 'list': 0.39; 'still': 0.40;
'advantage': 0.40; 'case.': 0.40; 'data.': 0.40; 'best': 0.61;
'method': 0.61; 'merge': 0.62; 'data,': 0.63; 'entire': 0.67;
'items': 0.68; 'cost': 0.69; 'speed': 0.71; 'practical': 0.84;
'battle': 0.84; 'feature,': 0.84; 'reversed': 0.84; 'uphill': 0.84
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to;
bh=RBN90DUm4nc0Na44ZT8wZ5195oSX/DWnOyvRlvDPHlM=;
b=VRx8d4DfOAKdQaBm09g9rYrsDlfxy1SW8IqGqwOoNVyTShxx4wdcMgSMhvexpdzMbO
sh6tqeFwfrWVfb6Pxk078ZDVhRuxdzG9T7yU9MUHWcExry+gymMJYA7Fo/IdneoKDCYx
Ii5/JybOV1xuBmhpEjOMifMX51iQ8Vc5Z7wHyFgBZJ7xHPlglDbjtZ0sUq3YCA6v7Kha
N94eBD9Vgh1354SBlUr4Pwa9igOW/KQEoKLJsMnrEt+o/WyMxEewq/hqymnZetXjHJG6
NX02qoYrSeNve5ihEfFxUWJeOXEBXZHyisn+zibHstuAVYOxgnAiid2+EtNtTfXtQx5a
R0BA==
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;
bh=RBN90DUm4nc0Na44ZT8wZ5195oSX/DWnOyvRlvDPHlM=;
b=eprn751eVD0f8xXmlyWi3ZIhVY88/3UxVKB7Z2b9XfGM8GK/nxmxRrmONxoN5eSuYN
xdcRPaL0aVQTKg1lgCEB6UhKrKmEOPrfF/SRLj0u7xCUmaMKdzrPz90yYTmC8Bniimdz
Tk7ruLT66N4DrSeGL79INXwaevQeJvYlgNp+xXYwxYWxteAneP5Lko/CIwN6+EYl5wM2
XigPRQ3ga9kyDxcdsi+bi4DR9fYxVIiAgCh+JHcm3MOaVwzWEyhJwVtnzQkrOz2sHmQM
LMnoYsQ/2VcuuF5KT5Mfgwubrr/56luMwvOufCjFgk7C5DHaPfNZEVOvXfLORVSLY18I
FYVw==
X-Gm-Message-State: AOAM530n/IwddysvYkDhP6GE6AsOlUJLPieIskW2oNOuepKEnXcH49Pp
LUULsZH2N0EU3yG9swHlmZBlgYeil4XPJJiDRWmBBciy
X-Google-Smtp-Source: ABdhPJyXHpjoKug2/R/2teZWJI+LHJoZ6GxmlQnwHs+4xqo6jcUviDaAULnrrOkybPpvjrw71NcLkxPY+SS9QevqfRI=
X-Received: by 2002:a5d:50c4:0:b0:20c:547d:1b4e with SMTP id
f4-20020a5d50c4000000b0020c547d1b4emr6559558wrt.160.1651448743910; Sun, 01
May 2022 16:45:43 -0700 (PDT)
In-Reply-To: <CAGGBd_otruOBmwWv5yhhRZB=BJ547pitiTCTODXwV0Km8OnMRw@mail.gmail.com>
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.39
Precedence: list
List-Id: General discussion list for the Python programming language
<python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>,
<mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <https://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>,
<mailto:python-list-request@python.org?subject=subscribe>
X-Mailman-Original-Message-ID: <CAPTjJmotvBiPTQC8bpYUS+y3Avrt1gyr5y5O6WCmVHNyWJiEHA@mail.gmail.com>
X-Mailman-Original-References: <CADs8Xt5LE4f5ayJ5n94+KKyR3bGQ13dk-Tr_u7XhFaEuwxpVOg@mail.gmail.com>
<CAPTjJmq3VgD+OyiL4W=m2Bo0BJwHaYY69a=mAPJx5vMnfBdHFg@mail.gmail.com>
<CAGGBd_p9iNwiAe87E1x759Oo659HTAO9Frs7L8fzpTq9+J0Rmg@mail.gmail.com>
<CAPTjJmpZEQSgzL2b50FK+mK7dNJgJwd2YteqjxyxWZi_o4UUJQ@mail.gmail.com>
<CAGGBd_otruOBmwWv5yhhRZB=BJ547pitiTCTODXwV0Km8OnMRw@mail.gmail.com>
 by: Chris Angelico - Sun, 1 May 2022 23:45 UTC

On Mon, 2 May 2022 at 09:20, Dan Stromberg <drsalists@gmail.com> wrote:
>
>
> On Sun, May 1, 2022 at 1:44 PM Chris Angelico <rosuav@gmail.com> wrote:
>>
>> On Mon, 2 May 2022 at 06:43, Dan Stromberg <drsalists@gmail.com> wrote:
>> > On Sun, May 1, 2022 at 11:10 AM Chris Angelico <rosuav@gmail.com> wrote:
>> >>
>> >> On Mon, 2 May 2022 at 01:53, Nas Bayedil <nbayedil@gmail.com> wrote:
>> >> > We believe that using this method to develop completely new, fast
>> >> > algorithms, approaching the speed of the famous *QuickSort*, the speed of
>> >> > which cannot be surpassed, but its drawback can be circumvented, in the
>> >> > sense of stack overflow, on some data.
>> >>
>> >> Hmm, actually TimSort *does* exceed the speed of quicksort for a lot
>> >> of real-world data. For instance, if you take a large sorted list,
>> >> append a handful of (unsorted) items to it, and then sort the list,
>> >> TimSort can take advantage of the fact that the bulk of the list is
>> >> sorted. It ends up significantly faster than re-sorting the entire
>> >> list.
>> >
>> >
>> > In fact, Timsort is O(n) for already-sorted data, while many quicksorts are O(n^2) for already-sorted data.
>> >
>> > Quicksort can be salvaged by using a median-of-3 partitioning, but it's still O(n^2) in the (less common) worst case.
>> >
>>
>> This is true, but purely sorted data isn't a very practical case. The
>> case of mostly-sorted data IS practical, though, so it's a quite big
>> win that it can be close to O(n), and still faster than inserting each
>> item individually.
>
>
> You seem to be of the impression that nearly-sorted data isn't an uphill battle with a straightforward quicksort.
>
> I'm having a hard time convincing myself of that.
>

The median-of-three partitioning technique makes that work reasonably
well, so it won't be pathologically slow. It's hardly Quicksort's best
feature, but it could easily be a lot worse. I'd have to check, but I
think it still manages to be O(n log n). Merge sort, of course, is a
lot more consistent, but the asymptotic cost is still broadly the
same.

But Timsort manages to be close to O(n) for sorted data, reversed
data, nearly-sorted or nearly-reversed data, etc. Makes it very handy
for jobs like "click a heading to sort by it", where you might add
multiple sort keys.

(Plus, Python's implementation has some cool tricks for small
collections that make it quite efficient.)

ChrisA

Re: new sorting algorithm

<6f6c624f-cc97-300a-1234-d6a0cf1d5d3b@earthlink.net>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=18108&group=comp.lang.python#18108

 copy link   Newsgroups: comp.lang.python
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!1.us.feeder.erje.net!3.us.feeder.erje.net!feeder.erje.net!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 02 May 2022 08:09:56 -0500
Message-ID: <6f6c624f-cc97-300a-1234-d6a0cf1d5d3b@earthlink.net>
Date: Mon, 2 May 2022 09:09:48 -0400
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.8.1
Subject: Re: new sorting algorithm
Content-Language: en-US
To: Chris Angelico <rosuav@gmail.com>
Newsgroups: comp.lang.python
References: <CADs8Xt5LE4f5ayJ5n94+KKyR3bGQ13dk-Tr_u7XhFaEuwxpVOg@mail.gmail.com>
<CAPTjJmq3VgD+OyiL4W=m2Bo0BJwHaYY69a=mAPJx5vMnfBdHFg@mail.gmail.com>
<CAGGBd_p9iNwiAe87E1x759Oo659HTAO9Frs7L8fzpTq9+J0Rmg@mail.gmail.com>
<CAPTjJmpZEQSgzL2b50FK+mK7dNJgJwd2YteqjxyxWZi_o4UUJQ@mail.gmail.com>
<CAGGBd_otruOBmwWv5yhhRZB=BJ547pitiTCTODXwV0Km8OnMRw@mail.gmail.com>
<CAPTjJmotvBiPTQC8bpYUS+y3Avrt1gyr5y5O6WCmVHNyWJiEHA@mail.gmail.com>
<mailman.289.1651448745.20749.python-list@python.org>
From: chot...@earthlink.net (charles hottel)
In-Reply-To: <mailman.289.1651448745.20749.python-list@python.org>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Lines: 64
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 100.15.117.46
X-Trace: sv3-Iaf2UCyMqzidvjay/5PI2s0tp9VtH7AcN7ktUJ2WsgLpb83YLWFGI5/wdwWy1Qkh5AKb9JiR9kKYAyv!vim9MtVyz2gJpeYVJ4zCOizd8o3wQGA02G5Z3EapAGfDmnlfQ0L2QP+PYo4Arx7GPFIepvUdnToF!VmOLsAj6aGxbyMN8ZIw=
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 4661
 by: charles hottel - Mon, 2 May 2022 13:09 UTC

On 5/1/2022 7:45 PM, Chris Angelico wrote:
> On Mon, 2 May 2022 at 09:20, Dan Stromberg <drsalists@gmail.com> wrote:
>>
>>
>> On Sun, May 1, 2022 at 1:44 PM Chris Angelico <rosuav@gmail.com> wrote:
>>>
>>> On Mon, 2 May 2022 at 06:43, Dan Stromberg <drsalists@gmail.com> wrote:
>>>> On Sun, May 1, 2022 at 11:10 AM Chris Angelico <rosuav@gmail.com> wrote:
>>>>>
>>>>> On Mon, 2 May 2022 at 01:53, Nas Bayedil <nbayedil@gmail.com> wrote:
>>>>>> We believe that using this method to develop completely new, fast
>>>>>> algorithms, approaching the speed of the famous *QuickSort*, the speed of
>>>>>> which cannot be surpassed, but its drawback can be circumvented, in the
>>>>>> sense of stack overflow, on some data.
>>>>>
>>>>> Hmm, actually TimSort *does* exceed the speed of quicksort for a lot
>>>>> of real-world data. For instance, if you take a large sorted list,
>>>>> append a handful of (unsorted) items to it, and then sort the list,
>>>>> TimSort can take advantage of the fact that the bulk of the list is
>>>>> sorted. It ends up significantly faster than re-sorting the entire
>>>>> list.
>>>>
>>>>
>>>> In fact, Timsort is O(n) for already-sorted data, while many quicksorts are O(n^2) for already-sorted data.
>>>>
>>>> Quicksort can be salvaged by using a median-of-3 partitioning, but it's still O(n^2) in the (less common) worst case.
>>>>
>>>
>>> This is true, but purely sorted data isn't a very practical case. The
>>> case of mostly-sorted data IS practical, though, so it's a quite big
>>> win that it can be close to O(n), and still faster than inserting each
>>> item individually.
>>
>>
>> You seem to be of the impression that nearly-sorted data isn't an uphill battle with a straightforward quicksort.
>>
>> I'm having a hard time convincing myself of that.
>>
>
> The median-of-three partitioning technique makes that work reasonably
> well, so it won't be pathologically slow. It's hardly Quicksort's best
> feature, but it could easily be a lot worse. I'd have to check, but I
> think it still manages to be O(n log n). Merge sort, of course, is a
> lot more consistent, but the asymptotic cost is still broadly the
> same.
>
> But Timsort manages to be close to O(n) for sorted data, reversed
> data, nearly-sorted or nearly-reversed data, etc. Makes it very handy
> for jobs like "click a heading to sort by it", where you might add
> multiple sort keys.
>
> (Plus, Python's implementation has some cool tricks for small
> collections that make it quite efficient.)
>
> ChrisA

Some versions of Quicksort switch over to Straight Insertion Sort when
the partitions become small enough. The correct size will vary depending
on the hardware.

I have not kept up with the latest improvements and I am not familiar
with TimSort. However Heapsort should always be O(n log n) and there
are modifications to Heapsort that can make it faster than vanilla
Heapsort and closer to the speed of Quicksort.

Re: new sorting algorithm

<mailman.300.1651520080.20749.python-list@python.org>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=18116&group=comp.lang.python#18116

 copy link   Newsgroups: comp.lang.python
Path: i2pn2.org!i2pn.org!news.swapon.de!fu-berlin.de!uni-berlin.de!not-for-mail
From: mat...@wichmann.us (Mats Wichmann)
Newsgroups: comp.lang.python
Subject: Re: new sorting algorithm
Date: Mon, 2 May 2022 13:18:36 -0600
Lines: 18
Message-ID: <mailman.300.1651520080.20749.python-list@python.org>
References: <CADs8Xt5LE4f5ayJ5n94+KKyR3bGQ13dk-Tr_u7XhFaEuwxpVOg@mail.gmail.com>
<CAPTjJmq3VgD+OyiL4W=m2Bo0BJwHaYY69a=mAPJx5vMnfBdHFg@mail.gmail.com>
<CAGGBd_p9iNwiAe87E1x759Oo659HTAO9Frs7L8fzpTq9+J0Rmg@mail.gmail.com>
<CAPTjJmpZEQSgzL2b50FK+mK7dNJgJwd2YteqjxyxWZi_o4UUJQ@mail.gmail.com>
<CAGGBd_otruOBmwWv5yhhRZB=BJ547pitiTCTODXwV0Km8OnMRw@mail.gmail.com>
<CAPTjJmotvBiPTQC8bpYUS+y3Avrt1gyr5y5O6WCmVHNyWJiEHA@mail.gmail.com>
<mailman.289.1651448745.20749.python-list@python.org>
<6f6c624f-cc97-300a-1234-d6a0cf1d5d3b@earthlink.net>
<a177367f-73a8-b20f-be7d-08e13e1b4b18@wichmann.us>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
X-Trace: news.uni-berlin.de qiGT+i851pW417dUzf/bpgo9OoKQ2e4xOcdO3sTVZkpg==
Return-Path: <mats@wichmann.us>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
Authentication-Results: mail.python.org; dkim=pass
reason="1024-bit key; unprotected key"
header.d=pobox.com header.i=@pobox.com header.b=vFIrlxc+;
dkim-adsp=none (unprotected policy); dkim-atps=neutral
X-Spam-Status: OK 0.158
X-Spam-Level: *
X-Spam-Evidence: '*H*': 0.70; '*S*': 0.02; 'enough.': 0.09; 'log':
0.12; 'hardware.': 0.16; 'insertion': 0.16; 'received:64.147':
0.16; 'wrote:': 0.16; 'to:addr:python-list': 0.20; 'url:wiki':
0.23; 'header:User-Agent:1': 0.30; 'url-ip:91/8': 0.32; 'there':
0.33; 'header:In-Reply-To:1': 0.34; 'received:192.168': 0.37;
'read': 0.38; 'should': 0.40; 'kept': 0.61; 'received:64': 0.67;
'order': 0.69; 'depending': 0.70; 'url:wikipedia': 0.70; 'speed':
0.71; 'vary': 0.76; 'quick': 0.77
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed; d=pobox.com; h=message-id
:date:mime-version:subject:to:references:from:in-reply-to
:content-type:content-transfer-encoding; s=sasl; bh=VfkIbQF+d2hS
i1ypUHC/QZ6ajMeNqZ7Bssmvwcm1bUY=; b=vFIrlxc+mlNuuy8kBXKNFRQuII+s
xUjdgF4bfPHmMAWK21EX1+fk/AiTgflcf3z0daASOTWdcLNPTPt2lxW/x4uT4ASG
DvSBqsNNHDuCRH5TBlYYZ9Des0M0ybfXodczW3X/vyRdqNwotmNZ7AKC8Bm7hPp6
FbUKAQ3HSrs4z1Q=
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed; d=wichmann.us;
h=message-id:date:mime-version:subject:to:references:from:in-reply-to:content-type:content-transfer-encoding;
s=2018-07.pbsmtp; bh=A9RdSVnsKpT950MBtVjs4hXkDPdGWw4qNena0IFz0Go=;
b=oslTPO3p6Qu7p/87ipoIvTKKa4sDe/zsDtZ2omDm3h670fdM2x2GreAURaWKCWEGDvySzxlLCAHuRhQHSAatBzEwagjlbI3gUrR/3cgifQHiCF0dnWZ03tZmcWgNdAnejjEHg+f/Ajo6rf70hQ17tLLt0E4KsiwdX4SpFas6lUI=
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101
Thunderbird/91.8.0
Content-Language: en-US
In-Reply-To: <6f6c624f-cc97-300a-1234-d6a0cf1d5d3b@earthlink.net>
X-Pobox-Relay-ID: AAEFBF28-CA4C-11EC-B7E5-CB998F0A682E-81526775!pb-smtp2.pobox.com
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.39
Precedence: list
List-Id: General discussion list for the Python programming language
<python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>,
<mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <https://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>,
<mailto:python-list-request@python.org?subject=subscribe>
X-Mailman-Original-Message-ID: <a177367f-73a8-b20f-be7d-08e13e1b4b18@wichmann.us>
X-Mailman-Original-References: <CADs8Xt5LE4f5ayJ5n94+KKyR3bGQ13dk-Tr_u7XhFaEuwxpVOg@mail.gmail.com>
<CAPTjJmq3VgD+OyiL4W=m2Bo0BJwHaYY69a=mAPJx5vMnfBdHFg@mail.gmail.com>
<CAGGBd_p9iNwiAe87E1x759Oo659HTAO9Frs7L8fzpTq9+J0Rmg@mail.gmail.com>
<CAPTjJmpZEQSgzL2b50FK+mK7dNJgJwd2YteqjxyxWZi_o4UUJQ@mail.gmail.com>
<CAGGBd_otruOBmwWv5yhhRZB=BJ547pitiTCTODXwV0Km8OnMRw@mail.gmail.com>
<CAPTjJmotvBiPTQC8bpYUS+y3Avrt1gyr5y5O6WCmVHNyWJiEHA@mail.gmail.com>
<mailman.289.1651448745.20749.python-list@python.org>
<6f6c624f-cc97-300a-1234-d6a0cf1d5d3b@earthlink.net>
 by: Mats Wichmann - Mon, 2 May 2022 19:18 UTC

On 5/2/22 07:09, charles hottel wrote:

> Some versions of Quicksort switch over to Straight Insertion Sort when
> the partitions become small enough. The correct size will vary depending
> on the hardware.
>
> I have not kept up with the latest improvements and I am not familiar
> with TimSort.  However Heapsort  should always be O(n log n) and there
> are modifications to Heapsort that can make it faster than vanilla
> Heapsort and closer to the speed of Quicksort.

A quick read might be in order then...

https://en.wikipedia.org/wiki/Timsort

1
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor