@@ -186,8 +186,8 @@ The `Timsort <https://en.wikipedia.org/wiki/Timsort>`_ algorithm used in Python
186186does multiple sorts efficiently because it can take advantage of any ordering
187187already present in a dataset.
188188
189- The Old Way Using Decorate-Sort-Undecorate
190- ==========================================
189+ Decorate-Sort-Undecorate
190+ ========================
191191
192192This idiom is called Decorate-Sort-Undecorate after its three steps:
193193
@@ -226,90 +226,36 @@ after Randal L. Schwartz, who popularized it among Perl programmers.
226226
227227Now that Python sorting provides key-functions, this technique is not often needed.
228228
229+ Comparison Functions
230+ ====================
229231
230- The Old Way Using the *cmp * Parameter
231- =====================================
232-
233- Many constructs given in this HOWTO assume Python 2.4 or later. Before that,
234- there was no:func: `sorted ` builtin and:meth: `list.sort ` took no keyword
235- arguments. Instead, all of the Py2.x versions supported a *cmp * parameter to
236- handle user specified comparison functions.
237-
238- In Py3.0, the *cmp * parameter was removed entirely (as part of a larger effort to
239- simplify and unify the language, eliminating the conflict between rich
240- comparisons and the:meth: `__cmp__ ` magic method).
241-
242- In Py2.x, sort allowed an optional function which can be called for doing the
243- comparisons. That function should take two arguments to be compared and then
244- return a negative value for less-than, return zero if they are equal, or return
245- a positive value for greater-than. For example, we can do:
246-
247- ..doctest ::
248-
249- >>>def numeric_compare (x ,y ):
250- ...return x- y
251- >>>sorted ([5 ,2 ,4 ,1 ,3 ],cmp = numeric_compare)# doctest: +SKIP
252- [1, 2, 3, 4, 5]
253-
254- Or you can reverse the order of comparison with:
255-
256- ..doctest ::
257-
258- >>>def reverse_numeric (x ,y ):
259- ...return y- x
260- >>>sorted ([5 ,2 ,4 ,1 ,3 ],cmp = reverse_numeric)# doctest: +SKIP
261- [5, 4, 3, 2, 1]
262-
263- When porting code from Python 2.x to 3.x, the situation can arise when you have
264- the user supplying a comparison function and you need to convert that to a key
265- function. The following wrapper makes that easy to do:
266-
267- ..testcode ::
268-
269- def cmp_to_key(mycmp):
270- 'Convert a cmp= function into a key= function'
271- class K:
272- def __init__(self, obj, *args):
273- self.obj = obj
274- def __lt__(self, other):
275- return mycmp(self.obj, other.obj) < 0
276- def __gt__(self, other):
277- return mycmp(self.obj, other.obj) > 0
278- def __eq__(self, other):
279- return mycmp(self.obj, other.obj) == 0
280- def __le__(self, other):
281- return mycmp(self.obj, other.obj) <= 0
282- def __ge__(self, other):
283- return mycmp(self.obj, other.obj) >= 0
284- def __ne__(self, other):
285- return mycmp(self.obj, other.obj) != 0
286- return K
287-
288- ..doctest ::
289- :hide:
232+ Unlike key functions that return an absolute value for sorting, a comparison
233+ function computes the relative ordering for two inputs.
290234
291- >>>sorted ([5 ,2 ,4 ,1 ,3 ],key = cmp_to_key(reverse_numeric))
292- [5, 4, 3, 2, 1]
235+ For example, a `balance scale
236+ <https://upload.wikimedia.org/wikipedia/commons/1/17/Balance_à_tabac_1850.JPG> `_
237+ compares two samples giving a relative ordering: lighter, equal, or heavier.
238+ Likewise, a comparison function such as ``cmp(a, b) `` will return a negative
239+ value for less-than, zero if the inputs are equal, or a positive value for
240+ greater-than.
293241
294- To convert to a key function, just wrap the old comparison function:
295-
296- ..testsetup ::
297-
298- from functools import cmp_to_key
299-
300- ..doctest ::
242+ It is common to encounter comparison functions when translating algorithms from
243+ other languages. Also, some libraries provide comparison functions as part of
244+ their API. For example,:func: `locale.strcoll ` is a comparison function.
301245
302- >>>sorted ([5 ,2 ,4 ,1 ,3 ],key = cmp_to_key(reverse_numeric))
303- [5, 4, 3, 2, 1]
246+ To accommodate those situations, Python provides
247+ :class: `functools.cmp_to_key ` to wrap the comparison function
248+ to make it usable as a key function::
304249
305- In Python 3.2, the:func: `functools.cmp_to_key ` function was added to the
306- :mod: `functools ` module in the standard library.
250+ sorted(words, key=cmp_to_key(strcoll)
307251
308252Odds and Ends
309253=============
310254
311255* For locale aware sorting, use:func: `locale.strxfrm ` for a key function or
312- :func: `locale.strcoll ` for a comparison function.
256+ :func: `locale.strcoll ` for a comparison function. This is necessary
257+ because "alphabetical" sort orderings can vary across cultures even
258+ if the underlying alphabet is the same.
313259
314260* The *reverse * parameter still maintains sort stability (so that records with
315261 equal keys retain the original order). Interestingly, that effect can be