Mailing List Archive

On 06/06/2021 11.42, Marco Sulla wrote:
> As title. Is it faster for inplace sorting, or simply the
> implementation of list.sort() was done before the implementation of
> timsort?

list.sort() uses timsort. What makes you think that Python uses mergesort?

Tim Peters invented timsort for Python about twenty years ago. Tim a
first generation Python core dev. Other languages like Java adopted
timsort from Python later.

Christian



_______________________________________________
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-leave@python.org
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/P7XFRAU6GL2CH6RBXPLGXEK4AL5KF2HV/
Code of Conduct: http://python.org/psf/codeofconduct/

On Sun, 6 Jun 2021 at 11:57, Christian Heimes <christian@python.org> wrote:
>
> On 06/06/2021 11.42, Marco Sulla wrote:
> > As title. Is it faster for inplace sorting, or simply the
> > implementation of list.sort() was done before the implementation of
> > timsort?
>
> list.sort() uses timsort. What makes you think that Python uses mergesort?

In listobject.c, in the comment above list_sort_impl, there's written
"An adaptive, stable, natural mergesort". But now I see that after
there is "See listsort.txt" where it's stated "This describes an
adaptive, stable, natural mergesort, modestly called timsort".

> Tim Peters invented timsort for Python about twenty years ago. Tim a
> first generation Python core dev. Other languages like Java adopted
> timsort from Python later.

I know. Thank you for the answer :)

>
> Christian
>
>
>
> _______________________________________________
> Python-Dev mailing list -- python-dev@python.org
> To unsubscribe send an email to python-dev-leave@python.org
> https://mail.python.org/mailman3/lists/python-dev.python.org/
> Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/P7XFRAU6GL2CH6RBXPLGXEK4AL5KF2HV/
> Code of Conduct: http://python.org/psf/codeofconduct/
_______________________________________________
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-leave@python.org
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/BGTTKCM4X6X24V2OZT3UHNHNBZSY5EP6/
Code of Conduct: http://python.org/psf/codeofconduct/

On Sun, Jun 6, 2021 at 2:46 AM Marco Sulla <Marco.Sulla.Python@gmail.com>
wrote:

> As title. Is it faster for inplace sorting, or simply the
> implementation of list.sort() was done before the implementation of
> timsort?
>

As you already know, timsort is pretty close to merge sort.

Timsort added the innovation of making mergesort in-place, plus a little
(though already common) O(*n^2) sorting for small sublists.

I've got a comparison of sort algorithms in both Cython and Pure Python
(your choice) at:
https://stromberg.dnsalias.org/~strombrg/sort-comparison/
...including a version of timsort that is in Cython or Pure Python.

HTH.

On Sun, Jun 06, 2021 at 04:07:57PM -0700, Dan Stromberg wrote:
> I've got a comparison of sort algorithms in both Cython and Pure Python (your
> choice) at:
> https://stromberg.dnsalias.org/~strombrg/sort-comparison/?
> ...including a version of timsort that is in Cython or Pure Python.
>

Interesting! timsort get's to near-linear in your benchmark.

--
Senthil
_______________________________________________
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-leave@python.org
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/PK2CURNB67WNDEQJQISAYNGRMB4BQ26N/
Code of Conduct: http://python.org/psf/codeofconduct/

On Mon, 7 Jun 2021 06:49:24 -0700
Senthil Kumaran <senthil@python.org> wrote:
> On Sun, Jun 06, 2021 at 04:07:57PM -0700, Dan Stromberg wrote:
> > I've got a comparison of sort algorithms in both Cython and Pure Python (your
> > choice) at:
> > https://stromberg.dnsalias.org/~strombrg/sort-comparison/ 
> > ...including a version of timsort that is in Cython or Pure Python.
> >
>
> Interesting! timsort get's to near-linear in your benchmark.

O(n log n) always looks linear when n is small enough...

Regards

Antoine.


_______________________________________________
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-leave@python.org
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/XU6JHUNZXPLG443Z62NFPXCJKGHLLLG4/
Code of Conduct: http://python.org/psf/codeofconduct/

On Sun, Jun 6, 2021 at 7:09 PM Dan Stromberg <drsalists@gmail.com> wrote:

> I've got a comparison of sort algorithms in both Cython and Pure Python
> (your choice) at:
> https://stromberg.dnsalias.org/~strombrg/sort-comparison/
> ...including a version of timsort that is in Cython or Pure Python.
>

Thanks for sharing the graphs. I found the performance of radix sort in
particular to be interesting to see mapped out visually, and have never
heard of "shellsort" prior to now. :)

[Dan Stromberg <drsalists@gmail.com>]
> ...
> Timsort added the innovation of making mergesort in-place, plus a little
> (though already common) O(*n^2) sorting for small sublists.

Actually, both were already very common in mergesorts. "timsort" is
much more a work of engineering than of insight ;-) That is, it
combined many pre-existing ideas, but pushed them hard, and got them
to work smoothly together.

The most novel part is "galloping" to vastly cut the number of
comparisons needed in many real-world cases of partially ordered
inputs. I took that idea from (as briefly explained in listsort.txt)
papers seeking to speed real-life unions and intersections of sorted
lists, presumably in database implementations. I later discovered
that the idea had already been applied to a mergesort, as noted in a
paper by McIlroy (cited in listsort.txt) - but the paper didn't give
any details, and best I can tell he never published his code.

WIthout that, timsort wouldn't have been worth the bother of writing -
it was generally no faster than Python's prior sort implementation on
randomly-ordered inputs, and is quite a large pile of code. But many
cases of real-world inputs do have significant pre-existing order of
some kind, where even a "perfect" quicksort (always picks _the_ median
as the partition pivot) remains O(n log n) but timsort O(n).

Curiously, though, it was the only implementation ever tried of a
mergesort-based algorithm that wasn't notably _slower_ on
randomly-ordered inputs than Python's prior "samplesort" algorithm
(like quicksort but with a very high-quality guess for the median
element based on recursively sample-sorting a largish random sample).
_______________________________________________
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-leave@python.org
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/Y22TRSA5I4JCNC6GRBX7QZYF4MLGPCYK/
Code of Conduct: http://python.org/psf/codeofconduct/

On Mon, Jun 7, 2021 at 11:20 AM Tim Peters <tim.peters@gmail.com> wrote:

> [Dan Stromberg <drsalists@gmail.com>]
> > ...
> > Timsort added the innovation of making mergesort in-place, plus a little
> > (though already common) O(*n^2) sorting for small sublists.
>
> Actually, both were already very common in mergesorts. "timsort" is
> much more a work of engineering than of insight ;-) That is, it
> combined many pre-existing ideas, but pushed them hard, and got them
> to work smoothly together.
>
> The most novel part is "galloping" to vastly cut the number of
> comparisons needed in many real-world cases of partially ordered
> inputs.
>

Thanks Tim.

Python itself is a great language, but in part it was your good-natured and
well-reasoned posts about Python that got me into Python instead of OCaml.