From 9f8a5b1abd7ef3fe387daf3ddeb6fe1bc11240b3 Mon Sep 17 00:00:00 2001 From: Ezio Melotti Date: Tue, 28 Oct 2014 12:57:11 +0100 Subject: [PATCH] #22237: document that sorted() is guaranteed to be stable. Initial patch by Martin Panter. --- Doc/library/functions.rst | 5 +++++ Doc/library/heapq.rst | 4 +++- Misc/ACKS | 1 + 3 files changed, 9 insertions(+), 1 deletion(-) diff --git a/Doc/library/functions.rst b/Doc/library/functions.rst index c4d1eaa40b..d8a3dcfb3e 100644 --- a/Doc/library/functions.rst +++ b/Doc/library/functions.rst @@ -1318,6 +1318,11 @@ available. They are listed here in alphabetical order. each element only once. Use :func:`functools.cmp_to_key` to convert an old-style *cmp* function to a *key* function. + The built-in :func:`sorted` function is guaranteed to be stable. A sort is + stable if it guarantees not to change the relative order of elements that + compare equal --- this is helpful for sorting in multiple passes (for + example, sort by department, then by salary grade). + For sorting examples and a brief sorting tutorial, see `Sorting HowTo `_\. diff --git a/Doc/library/heapq.rst b/Doc/library/heapq.rst index e8acd6c2e0..617e3fe630 100644 --- a/Doc/library/heapq.rst +++ b/Doc/library/heapq.rst @@ -136,7 +136,6 @@ pushing all values onto a heap and then popping off the smallest values one at a time:: >>> def heapsort(iterable): - ... 'Equivalent to sorted(iterable)' ... h = [] ... for value in iterable: ... heappush(h, value) @@ -145,6 +144,9 @@ time:: >>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] +This is similar to ``sorted(iterable)``, but unlike :func:`sorted`, this +implementation is not stable. + Heap elements can be tuples. This is useful for assigning comparison values (such as task priorities) alongside the main record being tracked:: diff --git a/Misc/ACKS b/Misc/ACKS index fad0d8856b..cf1cd619b1 100644 --- a/Misc/ACKS +++ b/Misc/ACKS @@ -1008,6 +1008,7 @@ Todd R. Palmer Juan David Ibáñez Palomar Jan Palus Yongzhi Pan +Martin Panter Mathias Panzenböck M. Papillon Peter Parente -- 2.50.1