classification
Title: sorted() docs should state that the sort is stable
Type: enhancement Stage: resolved
Components: Documentation Versions: Python 3.4, Python 3.5, Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: ezio.melotti Nosy List: Wilfred.Hughes, docs@python, ezio.melotti, georg.brandl, mark.dickinson, martin.panter, matrixise, python-dev, rhettinger
Priority: low Keywords: patch

Created on 2014-08-20 16:53 by Wilfred.Hughes, last changed 2014-10-28 13:00 by python-dev. This issue is now closed.

Files
File name Uploaded Description Edit
issue22237.patch matrixise, 2014-10-15 09:02 review
Messages (14)
msg225574 - (view) Author: Wilfred Hughes (Wilfred.Hughes) * Date: 2014-08-20 16:53
According to https://wiki.python.org/moin/HowTo/Sorting/#Sort_Stability_and_Complex_Sorts and Alex Martelli: http://stackoverflow.com/q/1915376/509706, Python's sorted() is stable. It would be great to update the docs for sorted() to state this.
msg225579 - (view) Author: Georg Brandl (georg.brandl) * (Python committer) Date: 2014-08-20 18:19
I agree: The docs for list.sort() do guarantee the stability, so sorted() should have the same indication.
msg225632 - (view) Author: Martin Panter (martin.panter) * (Python committer) Date: 2014-08-22 01:20
It looks like a fork of that how-to is actually part of the documentation: <https://docs.python.org/release/3.4.0/howto/sorting.html>. Perhaps the two should be linked better.

If “sorted” is indeed meant to be stable, that makes the docstring for the “heapsort” function <https://docs.python.org/release/3.4.0/library/heapq.html#basic-examples> invalid. That function is not stable, for example: heapsort((0, 0, False, 0)) -> [0, False, 0, 0].

Also, the how-to implicitly guarantees that only less-than (__lt__) is required for comparison. This is already documented for “list.sort”, but it might be good to add that guarantee to the “sorted” reference. Maybe also clarify if it applies (or not) to other sorting and comparison routines (e.g. heapq, bisect, min, max), though maybe that is straying off scope for this bug.
msg225647 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2014-08-22 06:05
I'll update the docs for sorted().
msg229316 - (view) Author: Stéphane Wirtel (matrixise) * (Python committer) Date: 2014-10-14 17:04
For this issue, I have read the source code of "sorted" and "list.sort" to be sure they use the same algorithm (not sure). But in the builtin_sorted function, I read PyId_sort, but when I grep the code, I don't find it. Where can I find the reference of this function?

Thank you.
msg229326 - (view) Author: Georg Brandl (georg.brandl) * (Python committer) Date: 2014-10-14 18:16
PyId_sort is not a function, it's a somewhat complicated way of getting a Python string "sort" (in this case, for looking up a method using PyObject_GetAttrId).  The string object is cached, with is faster than constructing one every time with PyObject_GetAttrString.
msg229415 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2014-10-15 08:38
> when I grep the code, I don't find it

The non-greppability is due to preprocessor evil. The culprit is this macro from Include/object.h:

  #define _Py_IDENTIFIER(varname) _Py_static_string(PyId_##varname, #varname)

along with the declaration

  _Py_IDENTIFIER(sort);

earlier in bltinmodule.c.
msg229416 - (view) Author: Stéphane Wirtel (matrixise) * (Python committer) Date: 2014-10-15 08:42
Hi Mark,

Without your explanation, I was really lost.

Thank you.
msg229419 - (view) Author: Stéphane Wirtel (matrixise) * (Python committer) Date: 2014-10-15 09:02
My patch for the documentation of Python 3.5, just need a small feedback.

If you agree with this patch, I will provide the same patch for 2.7 and 3.4

Thank you
msg229996 - (view) Author: Stéphane Wirtel (matrixise) * (Python committer) Date: 2014-10-25 13:32
ping.
msg230051 - (view) Author: Martin Panter (martin.panter) * (Python committer) Date: 2014-10-27 00:29
The new text seems reasonable to me on its own, however I still think the heapsort() docstring needs updating as well
msg230140 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2014-10-28 12:00
New changeset d44f7d229e00 by Ezio Melotti in branch '2.7':
#22237: document that sorted() is guaranteed to be stable.  Initial patch by Martin Panter.
https://hg.python.org/cpython/rev/d44f7d229e00

New changeset 5dd4906daa62 by Ezio Melotti in branch '3.4':
#22237: document that sorted() is guaranteed to be stable.  Initial patch by Martin Panter.
https://hg.python.org/cpython/rev/5dd4906daa62

New changeset b01568e2597e by Ezio Melotti in branch 'default':
#22237: merge with 3.4.
https://hg.python.org/cpython/rev/b01568e2597e
msg230141 - (view) Author: Ezio Melotti (ezio.melotti) * (Python committer) Date: 2014-10-28 12:02
Fixed, thanks for the patch!
msg230145 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2014-10-28 13:00
New changeset af8f678a4a75 by Ezio Melotti in branch '2.7':
#22237: fix patch attribution.
https://hg.python.org/cpython/rev/af8f678a4a75

New changeset 2f697bcc8f86 by Ezio Melotti in branch '3.4':
#22237: fix patch attribution.
https://hg.python.org/cpython/rev/2f697bcc8f86

New changeset 7e870ddd1989 by Ezio Melotti in branch 'default':
#22237: merge patch attribution fix.
https://hg.python.org/cpython/rev/7e870ddd1989
History
Date User Action Args
2014-10-28 13:00:13python-devsetmessages: + msg230145
2014-10-28 12:02:49ezio.melottisetstatus: open -> closed

assignee: rhettinger -> ezio.melotti

nosy: + ezio.melotti
messages: + msg230141
resolution: fixed
stage: resolved
2014-10-28 12:00:33python-devsetnosy: + python-dev
messages: + msg230140
2014-10-27 00:29:14martin.pantersetmessages: + msg230051
2014-10-25 13:32:23matrixisesetmessages: + msg229996
2014-10-15 09:02:53matrixisesetfiles: + issue22237.patch
keywords: + patch
messages: + msg229419
2014-10-15 08:42:00matrixisesetmessages: + msg229416
2014-10-15 08:38:26mark.dickinsonsetnosy: + mark.dickinson
messages: + msg229415
2014-10-14 18:16:13georg.brandlsetmessages: + msg229326
2014-10-14 17:04:05matrixisesetnosy: + matrixise
messages: + msg229316
2014-08-22 06:05:46rhettingersetpriority: normal -> low

messages: + msg225647
versions: - Python 3.1, Python 3.2, Python 3.3
2014-08-22 01:20:55martin.pantersetnosy: + martin.panter
messages: + msg225632
2014-08-20 19:55:04rhettingersetassignee: docs@python -> rhettinger

nosy: + rhettinger
2014-08-20 18:19:03georg.brandlsetnosy: + georg.brandl
messages: + msg225579
2014-08-20 16:53:50Wilfred.Hughescreate