Issue #1771: Remove cmp parameter from list.sort() and builtin.sorted().

10 files changed, 82 insertions, 265 deletions

diff --git a/Doc/library/functions.rst b/Doc/library/functions.rst
index 0126831..afa9198 100644
--- a/Doc/library/functions.rst
+++ b/Doc/library/functions.rst
@@ -959,31 +959,20 @@ available.  They are listed here in alphabetical order.
    ``a[start:stop:step]`` or ``a[start:stop, i]``.
 
 
-.. function:: sorted(iterable[, cmp[, key[, reverse]]])
+.. function:: sorted(iterable[, key[, reverse]])
 
    Return a new sorted list from the items in *iterable*.
 
-   The optional arguments *cmp*, *key*, and *reverse* have the same meaning as
+   The optional arguments *key* and *reverse* have the same meaning as
    those for the :meth:`list.sort` method (described in section
    :ref:`typesseq-mutable`).
 
-   *cmp* specifies a custom comparison function of two arguments (iterable
-   elements) which should return a negative, zero or positive number depending on
-   whether the first argument is considered smaller than, equal to, or larger than
-   the second argument: ``cmp=lambda x,y: cmp(x.lower(), y.lower())``.  The default
-   value is ``None``.
-
    *key* specifies a function of one argument that is used to extract a comparison
    key from each list element: ``key=str.lower``.  The default value is ``None``.
 
    *reverse* is a boolean value.  If set to ``True``, then the list elements are
    sorted as if each comparison were reversed.
 
-   In general, the *key* and *reverse* conversion processes are much faster than
-   specifying an equivalent *cmp* function.  This is because *cmp* is called
-   multiple times for each list element while *key* and *reverse* touch each
-   element only once.
-
 
 .. function:: staticmethod(function)
 
diff --git a/Doc/library/stdtypes.rst b/Doc/library/stdtypes.rst
index 22ca0f0..6a2be28 100644
--- a/Doc/library/stdtypes.rst
+++ b/Doc/library/stdtypes.rst
@@ -1266,8 +1266,7 @@ Note that while lists allow their items to be of any type, bytearray object
 | ``s.reverse()``              | reverses the items of *s* in   | \(6)                |
 |                              | place                          |                     |
 +------------------------------+--------------------------------+---------------------+
-| ``s.sort([cmp[, key[,        | sort the items of *s* in place | (6), (7)            |
-| reverse]]])``                |                                |                     |
+| ``s.sort([key[, reverse]])`` | sort the items of *s* in place | (6), (7)            |
 +------------------------------+--------------------------------+---------------------+
 
 .. index::
@@ -1321,23 +1320,12 @@ Notes:
    The :meth:`sort` method takes optional arguments for controlling the
    comparisons.
 
-   *cmp* specifies a custom comparison function of two arguments (list items) which
-   should return a negative, zero or positive number depending on whether the first
-   argument is considered smaller than, equal to, or larger than the second
-   argument: ``cmp=lambda x,y: cmp(x.lower(), y.lower())``.  The default value
-   is ``None``.
-
    *key* specifies a function of one argument that is used to extract a comparison
    key from each list element: ``key=str.lower``.  The default value is ``None``.
 
    *reverse* is a boolean value.  If set to ``True``, then the list elements are
    sorted as if each comparison were reversed.
 
-   In general, the *key* and *reverse* conversion processes are much faster than
-   specifying an equivalent *cmp* function.  This is because *cmp* is called
-   multiple times for each list element while *key* and *reverse* touch each
-   element only once.
-
    Starting with Python 2.3, the :meth:`sort` method 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
diff --git a/Lib/cookielib.py b/Lib/cookielib.py
index 4552412..ee31f46 100644
--- a/Lib/cookielib.py
+++ b/Lib/cookielib.py
@@ -1255,8 +1255,7 @@ class CookieJar:
 
         """
         # add cookies in order of most specific (ie. longest) path first
-        def decreasing_size(a, b): return cmp(len(b.path), len(a.path))
-        cookies.sort(decreasing_size)
+        cookies.sort(key=lambda a: len(a.path), reverse=True)
 
         version_set = False
 
diff --git a/Lib/pstats.py b/Lib/pstats.py
index 39f1b64..3e6e994 100644
--- a/Lib/pstats.py
+++ b/Lib/pstats.py
@@ -238,7 +238,7 @@ class Stats:
             stats_list.append((cc, nc, tt, ct) + func +
                               (func_std_string(func), func))
 
-        stats_list.sort(TupleComp(sort_tuple).compare)
+        stats_list.sort(key=CmpToKey(TupleComp(sort_tuple).compare))
 
         self.fcn_list = fcn_list = []
         for tuple in stats_list:
@@ -470,6 +470,16 @@ class TupleComp:
                 return direction
         return 0
 
+def CmpToKey(mycmp):
+    'Convert a cmp= function into a key= function'
+    class K(object):
+        def __init__(self, obj):
+            self.obj = obj
+        def __lt__(self, other):
+            return mycmp(self.obj, other.obj) == -1
+    return K
+
+
 #**************************************************************************
 # func_name is a triple (file:string, line:int, name:string)
 
diff --git a/Lib/test/list_tests.py b/Lib/test/list_tests.py
index f03cdfe..49283e4 100644
--- a/Lib/test/list_tests.py
+++ b/Lib/test/list_tests.py
@@ -8,6 +8,15 @@ import os
 import unittest
 from test import test_support, seq_tests
 
+def CmpToKey(mycmp):
+    'Convert a cmp= function into a key= function'
+    class K(object):
+        def __init__(self, obj):
+            self.obj = obj
+        def __lt__(self, other):
+            return mycmp(self.obj, other.obj) == -1
+    return K
+
 class CommonTest(seq_tests.CommonTest):
 
     def test_init(self):
@@ -430,23 +439,21 @@ class CommonTest(seq_tests.CommonTest):
 
         def revcmp(a, b):
             return cmp(b, a)
-        u.sort(revcmp)
+        u.sort(key=CmpToKey(revcmp))
         self.assertEqual(u, self.type2test([2,1,0,-1,-2]))
 
         # The following dumps core in unpatched Python 1.5:
         def myComparison(x,y):
             return cmp(x%3, y%7)
         z = self.type2test(range(12))
-        z.sort(myComparison)
+        z.sort(key=CmpToKey(myComparison))
 
         self.assertRaises(TypeError, z.sort, 2)
 
         def selfmodifyingComparison(x,y):
             z.append(1)
             return cmp(x, y)
-        self.assertRaises(ValueError, z.sort, selfmodifyingComparison)
-
-        self.assertRaises(TypeError, z.sort, lambda x, y: 's')
+        self.assertRaises(ValueError, z.sort, key=CmpToKey(selfmodifyingComparison))
 
         self.assertRaises(TypeError, z.sort, 42, 42, 42, 42)
 
diff --git a/Lib/test/test_builtin.py b/Lib/test/test_builtin.py
index 92c1d00..8582862 100644
--- a/Lib/test/test_builtin.py
+++ b/Lib/test/test_builtin.py
@@ -1764,9 +1764,6 @@ class TestSorted(unittest.TestCase):
 
         data.reverse()
         random.shuffle(copy)
-        self.assertEqual(data, sorted(copy, cmp=lambda x, y: (x < y) - (x > y)))
-        self.assertNotEqual(data, copy)
-        random.shuffle(copy)
         self.assertEqual(data, sorted(copy, key=lambda x: -x))
         self.assertNotEqual(data, copy)
         random.shuffle(copy)
diff --git a/Lib/test/test_sort.py b/Lib/test/test_sort.py
index 8ef98c7..8301c31 100644
--- a/Lib/test/test_sort.py
+++ b/Lib/test/test_sort.py
@@ -6,6 +6,15 @@ import unittest
 verbose = test_support.verbose
 nerrors = 0
 
+def CmpToKey(mycmp):
+    'Convert a cmp= function into a key= function'
+    class K(object):
+        def __init__(self, obj):
+            self.obj = obj
+        def __lt__(self, other):
+            return mycmp(self.obj, other.obj) == -1
+    return K
+
 def check(tag, expected, raw, compare=None):
     global nerrors
 
@@ -14,7 +23,7 @@ def check(tag, expected, raw, compare=None):
 
     orig = raw[:]   # save input in case of error
     if compare:
-        raw.sort(compare)
+        raw.sort(key=CmpToKey(compare))
     else:
         raw.sort()
 
@@ -99,7 +108,7 @@ class TestBase(unittest.TestCase):
                 print("    Checking against an insane comparison function.")
                 print("        If the implementation isn't careful, this may segfault.")
             s = x[:]
-            s.sort(lambda a, b:  int(random.random() * 3) - 1)
+            s.sort(key=CmpToKey(lambda a, b:  int(random.random() * 3) - 1))
             check("an insane function left some permutation", x, s)
 
             x = [Complains(i) for i in x]
@@ -141,14 +150,6 @@ class TestBugs(unittest.TestCase):
         L = [C() for i in range(50)]
         self.assertRaises(ValueError, L.sort)
 
-    def test_cmpNone(self):
-        # Testing None as a comparison function.
-
-        L = list(range(50))
-        random.shuffle(L)
-        L.sort(None)
-        self.assertEqual(L, list(range(50)))
-
     def test_undetected_mutation(self):
         # Python 2.4a1 did not always detect mutation
         memorywaster = []
@@ -158,12 +159,12 @@ class TestBugs(unittest.TestCase):
                 L.pop()
                 return cmp(x, y)
             L = [1,2]
-            self.assertRaises(ValueError, L.sort, mutating_cmp)
+            self.assertRaises(ValueError, L.sort, key=CmpToKey(mutating_cmp))
             def mutating_cmp(x, y):
                 L.append(3)
                 del L[:]
                 return cmp(x, y)
-            self.assertRaises(ValueError, L.sort, mutating_cmp)
+            self.assertRaises(ValueError, L.sort, key=CmpToKey(mutating_cmp))
             memorywaster = [memorywaster]
 
 #==============================================================================
@@ -175,11 +176,11 @@ class TestDecorateSortUndecorate(unittest.TestCase):
         copy = data[:]
         random.shuffle(data)
         data.sort(key=str.lower)
-        copy.sort(cmp=lambda x,y: cmp(x.lower(), y.lower()))
+        copy.sort(key=CmpToKey(lambda x,y: cmp(x.lower(), y.lower())))
 
     def test_baddecorator(self):
         data = 'The quick Brown fox Jumped over The lazy Dog'.split()
-        self.assertRaises(TypeError, data.sort, None, lambda x,y: 0)
+        self.assertRaises(TypeError, data.sort, key=lambda x,y: 0)
 
     def test_stability(self):
         data = [(random.randrange(100), i) for i in range(200)]
@@ -188,25 +189,11 @@ class TestDecorateSortUndecorate(unittest.TestCase):
         copy.sort()                     # sort using both fields
         self.assertEqual(data, copy)    # should get the same result
 
-    def test_cmp_and_key_combination(self):
-        # Verify that the wrapper has been removed
-        def compare(x, y):
-            self.assertEqual(type(x), str)
-            self.assertEqual(type(x), str)
-            return cmp(x, y)
-        data = 'The quick Brown fox Jumped over The lazy Dog'.split()
-        data.sort(cmp=compare, key=str.lower)
-
-    def test_badcmp_with_key(self):
-        # Verify that the wrapper has been removed
-        data = 'The quick Brown fox Jumped over The lazy Dog'.split()
-        self.assertRaises(TypeError, data.sort, "bad", str.lower)
-
     def test_key_with_exception(self):
         # Verify that the wrapper has been removed
         data = list(range(-2, 2))
         dup = data[:]
-        self.assertRaises(ZeroDivisionError, data.sort, None, lambda x: 1/x)
+        self.assertRaises(ZeroDivisionError, data.sort, key=lambda x: 1/x)
         self.assertEqual(data, dup)
 
     def test_key_with_mutation(self):
@@ -254,14 +241,13 @@ class TestDecorateSortUndecorate(unittest.TestCase):
         random.shuffle(data)
         data.sort(reverse=True)
         self.assertEqual(data, list(range(99,-1,-1)))
-        self.assertRaises(TypeError, data.sort, "wrong type")
 
     def test_reverse_stability(self):
         data = [(random.randrange(100), i) for i in range(200)]
         copy1 = data[:]
         copy2 = data[:]
-        data.sort(cmp=lambda x,y: cmp(x[0],y[0]), reverse=True)
-        copy1.sort(cmp=lambda x,y: cmp(y[0],x[0]))
+        data.sort(key=CmpToKey(lambda x,y: cmp(x[0],y[0])), reverse=True)
+        copy1.sort(key=CmpToKey(lambda x,y: cmp(y[0],x[0])))
         self.assertEqual(data, copy1)
         copy2.sort(key=lambda x: x[0], reverse=True)
         self.assertEqual(data, copy2)
diff --git a/Misc/NEWS b/Misc/NEWS
index 7956e9c..6b7b692 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -14,6 +14,8 @@ Core and Builtins
 
 - Issue #1973: bytes.fromhex('') raises SystemError
 
+- Issue #1771: remove cmp parameter from sorted() and list.sort()
+
 - Issue #1969: split and rsplit in bytearray are inconsistent
 
 - map() and itertools.imap() no longer accept None for the first argument.
diff --git a/Objects/listobject.c b/Objects/listobject.c
index 4bc5ca9..a36a29e 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -888,64 +888,17 @@ reverse_slice(PyObject **lo, PyObject **hi)
  * pieces to this algorithm; read listsort.txt for overviews and details.
  */
 
-/* Comparison function.  Takes care of calling a user-supplied
- * comparison function (any callable Python object), which must not be
- * NULL (use the ISLT macro if you don't know, or call PyObject_RichCompareBool
- * with Py_LT if you know it's NULL).
+/* Comparison function: PyObject_RichCompareBool with Py_LT.
  * Returns -1 on error, 1 if x < y, 0 if x >= y.
  */
-static int
-islt(PyObject *x, PyObject *y, PyObject *compare)
-{
-	PyObject *res;
-	PyObject *args;
-	Py_ssize_t i;
 
-	assert(compare != NULL);
-	/* Call the user's comparison function and translate the 3-way
-	 * result into true or false (or error).
-	 */
-	args = PyTuple_New(2);
-	if (args == NULL)
-		return -1;
-	Py_INCREF(x);
-	Py_INCREF(y);
-	PyTuple_SET_ITEM(args, 0, x);
-	PyTuple_SET_ITEM(args, 1, y);
-	res = PyObject_Call(compare, args, NULL);
-	Py_DECREF(args);
-	if (res == NULL)
-		return -1;
-	if (!PyLong_CheckExact(res)) {
-		PyErr_Format(PyExc_TypeError,
-			     "comparison function must return int, not %.200s",
-			     res->ob_type->tp_name);
-		Py_DECREF(res);
-		return -1;
-	}
-	i = PyLong_AsLong(res);
-	Py_DECREF(res);
-	if (i == -1 && PyErr_Occurred()) {
-		/* Overflow in long conversion. */
-		return -1;
-	}
-	return i < 0;
-}
-
-/* If COMPARE is NULL, calls PyObject_RichCompareBool with Py_LT, else calls
- * islt.  This avoids a layer of function call in the usual case, and
- * sorting does many comparisons.
- * Returns -1 on error, 1 if x < y, 0 if x >= y.
- */
-#define ISLT(X, Y, COMPARE) ((COMPARE) == NULL ?			\
-			     PyObject_RichCompareBool(X, Y, Py_LT) :	\
-			     islt(X, Y, COMPARE))
+#define ISLT(X, Y) (PyObject_RichCompareBool(X, Y, Py_LT))
 
 /* Compare X to Y via "<".  Goto "fail" if the comparison raises an
    error.  Else "k" is set to true iff X<Y, and an "if (k)" block is
    started.  It makes more sense in context <wink>.  X and Y are PyObject*s.
 */
-#define IFLT(X, Y) if ((k = ISLT(X, Y, compare)) < 0) goto fail;  \
+#define IFLT(X, Y) if ((k = ISLT(X, Y)) < 0) goto fail;  \
 		   if (k)
 
 /* binarysort is the best method for sorting small arrays: it does
@@ -960,8 +913,7 @@ islt(PyObject *x, PyObject *y, PyObject *compare)
    the input (nothing is lost or duplicated).
 */
 static int
-binarysort(PyObject **lo, PyObject **hi, PyObject **start, PyObject *compare)
-     /* compare -- comparison function object, or NULL for default */
+binarysort(PyObject **lo, PyObject **hi, PyObject **start)
 {
 	register Py_ssize_t k;
 	register PyObject **l, **p, **r;
@@ -1026,7 +978,7 @@ elements to get out of order).
 Returns -1 in case of error.
 */
 static Py_ssize_t
-count_run(PyObject **lo, PyObject **hi, PyObject *compare, int *descending)
+count_run(PyObject **lo, PyObject **hi, int *descending)
 {
 	Py_ssize_t k;
 	Py_ssize_t n;
@@ -1081,7 +1033,7 @@ key, and the last n-k should follow key.
 Returns -1 on error.  See listsort.txt for info on the method.
 */
 static Py_ssize_t
-gallop_left(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint, PyObject *compare)
+gallop_left(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
 {
 	Py_ssize_t ofs;
 	Py_ssize_t lastofs;
@@ -1172,7 +1124,7 @@ we're sticking to "<" comparisons that it's much harder to follow if
 written as one routine with yet another "left or right?" flag.
 */
 static Py_ssize_t
-gallop_right(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint, PyObject *compare)
+gallop_right(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
 {
 	Py_ssize_t ofs;
 	Py_ssize_t lastofs;
@@ -1273,9 +1225,6 @@ struct s_slice {
 };
 
 typedef struct s_MergeState {
-	/* The user-supplied comparison function. or NULL if none given. */
-	PyObject *compare;
-
 	/* This controls when we get *into* galloping mode.  It's initialized
 	 * to MIN_GALLOP.  merge_lo and merge_hi tend to nudge it higher for
 	 * random data, and lower for highly structured data.
@@ -1306,10 +1255,9 @@ typedef struct s_MergeState {
 
 /* Conceptually a MergeState's constructor. */
 static void
-merge_init(MergeState *ms, PyObject *compare)
+merge_init(MergeState *ms)
 {
 	assert(ms != NULL);
-	ms->compare = compare;
 	ms->a = ms->temparray;
 	ms->alloced = MERGESTATE_TEMP_SIZE;
 	ms->n = 0;
@@ -1366,7 +1314,6 @@ merge_lo(MergeState *ms, PyObject **pa, Py_ssize_t na,
                          PyObject **pb, Py_ssize_t nb)
 {
 	Py_ssize_t k;
-	PyObject *compare;
 	PyObject **dest;
 	int result = -1;	/* guilty until proved innocent */
 	Py_ssize_t min_gallop;
@@ -1386,7 +1333,6 @@ merge_lo(MergeState *ms, PyObject **pa, Py_ssize_t na,
 		goto CopyB;
 
 	min_gallop = ms->min_gallop;
-	compare = ms->compare;
 	for (;;) {
 		Py_ssize_t acount = 0;	/* # of times A won in a row */
 		Py_ssize_t bcount = 0;	/* # of times B won in a row */
@@ -1396,7 +1342,7 @@ merge_lo(MergeState *ms, PyObject **pa, Py_ssize_t na,
 		 */
  		for (;;) {
  			assert(na > 1 && nb > 0);
-	 		k = ISLT(*pb, *pa, compare);
+	 		k = ISLT(*pb, *pa);
 			if (k) {
 				if (k < 0)
 					goto Fail;
@@ -1431,7 +1377,7 @@ merge_lo(MergeState *ms, PyObject **pa, Py_ssize_t na,
  			assert(na > 1 && nb > 0);
 			min_gallop -= min_gallop > 1;
 	 		ms->min_gallop = min_gallop;
-			k = gallop_right(*pb, pa, na, 0, compare);
+			k = gallop_right(*pb, pa, na, 0);
 			acount = k;
 			if (k) {
 				if (k < 0)
@@ -1454,7 +1400,7 @@ merge_lo(MergeState *ms, PyObject **pa, Py_ssize_t na,
 			if (nb == 0)
 				goto Succeed;
 
- 			k = gallop_left(*pa, pb, nb, 0, compare);
+ 			k = gallop_left(*pa, pb, nb, 0);
  			bcount = k;
 			if (k) {
 				if (k < 0)
@@ -1498,7 +1444,6 @@ static Py_ssize_t
 merge_hi(MergeState *ms, PyObject **pa, Py_ssize_t na, PyObject **pb, Py_ssize_t nb)
 {
 	Py_ssize_t k;
-	PyObject *compare;
 	PyObject **dest;
 	int result = -1;	/* guilty until proved innocent */
 	PyObject **basea;
@@ -1523,7 +1468,6 @@ merge_hi(MergeState *ms, PyObject **pa, Py_ssize_t na, PyObject **pb, Py_ssize_t
 		goto CopyA;
 
 	min_gallop = ms->min_gallop;
-	compare = ms->compare;
 	for (;;) {
 		Py_ssize_t acount = 0;	/* # of times A won in a row */
 		Py_ssize_t bcount = 0;	/* # of times B won in a row */
@@ -1533,7 +1477,7 @@ merge_hi(MergeState *ms, PyObject **pa, Py_ssize_t na, PyObject **pb, Py_ssize_t
 		 */
  		for (;;) {
  			assert(na > 0 && nb > 1);
-	 		k = ISLT(*pb, *pa, compare);
+	 		k = ISLT(*pb, *pa);
 			if (k) {
 				if (k < 0)
 					goto Fail;
@@ -1568,7 +1512,7 @@ merge_hi(MergeState *ms, PyObject **pa, Py_ssize_t na, PyObject **pb, Py_ssize_t
  			assert(na > 0 && nb > 1);
 			min_gallop -= min_gallop > 1;
 	 		ms->min_gallop = min_gallop;
-			k = gallop_right(*pb, basea, na, na-1, compare);
+			k = gallop_right(*pb, basea, na, na-1);
 			if (k < 0)
 				goto Fail;
 			k = na - k;
@@ -1586,7 +1530,7 @@ merge_hi(MergeState *ms, PyObject **pa, Py_ssize_t na, PyObject **pb, Py_ssize_t
 			if (nb == 1)
 				goto CopyA;
 
- 			k = gallop_left(*pa, baseb, nb, nb-1, compare);
+ 			k = gallop_left(*pa, baseb, nb, nb-1);
 			if (k < 0)
 				goto Fail;
 			k = nb - k;
@@ -1638,7 +1582,6 @@ merge_at(MergeState *ms, Py_ssize_t i)
 	PyObject **pa, **pb;
 	Py_ssize_t na, nb;
 	Py_ssize_t k;
-	PyObject *compare;
 
 	assert(ms != NULL);
 	assert(ms->n >= 2);
@@ -1664,8 +1607,7 @@ merge_at(MergeState *ms, Py_ssize_t i)
 	/* Where does b start in a?  Elements in a before that can be
 	 * ignored (already in place).
 	 */
-	compare = ms->compare;
-	k = gallop_right(*pb, pa, na, 0, compare);
+	k = gallop_right(*pb, pa, na, 0);
 	if (k < 0)
 		return -1;
 	pa += k;
@@ -1676,7 +1618,7 @@ merge_at(MergeState *ms, Py_ssize_t i)
 	/* Where does a end in b?  Elements in b after that can be
 	 * ignored (already in place).
 	 */
-	nb = gallop_left(pa[na-1], pb, nb, nb-1, compare);
+	nb = gallop_left(pa[na-1], pb, nb, nb-1);
 	if (nb <= 0)
 		return nb;
 
@@ -1771,8 +1713,8 @@ merge_compute_minrun(Py_ssize_t n)
    pattern.  Holds a key which is used for comparisons and the original record
    which is returned during the undecorate phase.  By exposing only the key
    during comparisons, the underlying sort stability characteristics are left
-   unchanged.  Also, if a custom comparison function is used, it will only see
-   the key instead of a full record. */
+   unchanged.  Also, the comparison function will only see the key instead of
+   a full record. */
 
 typedef struct {
 	PyObject_HEAD
@@ -1866,104 +1808,6 @@ sortwrapper_getvalue(PyObject *so)
 	return value;
 }
 
-/* Wrapper for user specified cmp functions in combination with a
-   specified key function.  Makes sure the cmp function is presented
-   with the actual key instead of the sortwrapper */
-
-typedef struct {
-	PyObject_HEAD
-	PyObject *func;
-} cmpwrapperobject;
-
-static void
-cmpwrapper_dealloc(cmpwrapperobject *co)
-{
-	Py_XDECREF(co->func);
-	PyObject_Del(co);
-}
-
-static PyObject *
-cmpwrapper_call(cmpwrapperobject *co, PyObject *args, PyObject *kwds)
-{
-	PyObject *x, *y, *xx, *yy;
-
-	if (!PyArg_UnpackTuple(args, "", 2, 2, &x, &y))
-		return NULL;
-	if (!PyObject_TypeCheck(x, &PySortWrapper_Type) ||
-	    !PyObject_TypeCheck(y, &PySortWrapper_Type)) {
-		PyErr_SetString(PyExc_TypeError,
-			"expected a sortwrapperobject");
-		return NULL;
-	}
-	xx = ((sortwrapperobject *)x)->key;
-	yy = ((sortwrapperobject *)y)->key;
-	return PyObject_CallFunctionObjArgs(co->func, xx, yy, NULL);
-}
-
-PyDoc_STRVAR(cmpwrapper_doc, "cmp() wrapper for sort with custom keys.");
-
-PyTypeObject PyCmpWrapper_Type = {
-	PyVarObject_HEAD_INIT(&PyType_Type, 0)
-	"cmpwrapper",				/* tp_name */
-	sizeof(cmpwrapperobject),		/* tp_basicsize */
-	0,					/* tp_itemsize */
-	/* methods */
-	(destructor)cmpwrapper_dealloc,		/* tp_dealloc */
-	0,					/* tp_print */
-	0,					/* tp_getattr */
-	0,					/* tp_setattr */
-	0,					/* tp_compare */
-	0,					/* tp_repr */
-	0,					/* tp_as_number */
-	0,					/* tp_as_sequence */
-	0,					/* tp_as_mapping */
-	0,					/* tp_hash */
-	(ternaryfunc)cmpwrapper_call,		/* tp_call */
-	0,					/* tp_str */
-	PyObject_GenericGetAttr,		/* tp_getattro */
-	0,					/* tp_setattro */
-	0,					/* tp_as_buffer */
-	Py_TPFLAGS_DEFAULT,			/* tp_flags */
-	cmpwrapper_doc,				/* tp_doc */
-};
-
-static PyObject *
-build_cmpwrapper(PyObject *cmpfunc)
-{
-	cmpwrapperobject *co;
-
-	co = PyObject_New(cmpwrapperobject, &PyCmpWrapper_Type);
-	if (co == NULL)
-		return NULL;
-	Py_INCREF(cmpfunc);
-	co->func = cmpfunc;
-	return (PyObject *)co;
-}
-
-static int
-is_default_cmp(PyObject *cmpfunc)
-{
-	PyCFunctionObject *f;
-	const char *module;
-	if (cmpfunc == NULL || cmpfunc == Py_None)
-		return 1;
-	if (!PyCFunction_Check(cmpfunc))
-		return 0;
-	f = (PyCFunctionObject *)cmpfunc;
-	if (f->m_self != NULL)
-		return 0;
-	if (!PyUnicode_Check(f->m_module))
-		return 0;
-	module = PyUnicode_AsString(f->m_module);
-	if (module == NULL)
-		return 0;
-	if (strcmp(module, "builtins") != 0)
-		return 0;
-	if (strcmp(f->m_ml->ml_name, "cmp") != 0)
-		return 0;
-	return 1;
-}
-
 /* An adaptive, stable, natural mergesort.  See listsort.txt.
  * Returns Py_None on success, NULL on error.  Even in case of error, the
  * list will be some permutation of its input state (nothing is lost or
@@ -1979,31 +1823,27 @@ listsort(PyListObject *self, PyObject *args, PyObject *kwds)
 	Py_ssize_t saved_ob_size, saved_allocated;
 	PyObject **saved_ob_item;
 	PyObject **final_ob_item;
-	PyObject *compare = NULL;
 	PyObject *result = NULL;	/* guilty until proved innocent */
 	int reverse = 0;
 	PyObject *keyfunc = NULL;
 	Py_ssize_t i;
 	PyObject *key, *value, *kvpair;
-	static char *kwlist[] = {"cmp", "key", "reverse", 0};
+	static char *kwlist[] = {"key", "reverse", 0};
 
 	assert(self != NULL);
 	assert (PyList_Check(self));
 	if (args != NULL) {
-		if (!PyArg_ParseTupleAndKeywords(args, kwds, "|OOi:sort",
-			kwlist, &compare, &keyfunc, &reverse))
+		if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:sort",
+			kwlist, &keyfunc, &reverse))
+			return NULL;
+		if (Py_SIZE(args) > 0) {
+			PyErr_SetString(PyExc_TypeError,
+				"must use keyword argument for key function");
 			return NULL;
+		}
 	}
-	if (is_default_cmp(compare))
-		compare = NULL;
 	if (keyfunc == Py_None)
 		keyfunc = NULL;
-	if (compare != NULL && keyfunc != NULL) {
-		compare = build_cmpwrapper(compare);
-		if (compare == NULL)
-			return NULL;
-	} else
-		Py_XINCREF(compare);
 
 	/* The list is temporarily made empty, so that mutations performed
 	 * by comparison functions can't affect the slice of memory we're
@@ -2043,7 +1883,7 @@ listsort(PyListObject *self, PyObject *args, PyObject *kwds)
 	if (reverse && saved_ob_size > 1)
 		reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);
 
-	merge_init(&ms, compare);
+	merge_init(&ms);
 
 	nremaining = saved_ob_size;
 	if (nremaining < 2)
@@ -2060,7 +1900,7 @@ listsort(PyListObject *self, PyObject *args, PyObject *kwds)
 		Py_ssize_t n;
 
 		/* Identify next run. */
-		n = count_run(lo, hi, compare, &descending);
+		n = count_run(lo, hi, &descending);
 		if (n < 0)
 			goto fail;
 		if (descending)
@@ -2069,7 +1909,7 @@ listsort(PyListObject *self, PyObject *args, PyObject *kwds)
 		if (n < minrun) {
 			const Py_ssize_t force = nremaining <= minrun ?
 	 			  	  nremaining : minrun;
-			if (binarysort(lo, lo + force, lo + n, compare) < 0)
+			if (binarysort(lo, lo + force, lo + n) < 0)
 				goto fail;
 			n = force;
 		}
@@ -2131,7 +1971,6 @@ dsu_fail:
 		}
 		PyMem_FREE(final_ob_item);
 	}
-	Py_XDECREF(compare);
 	Py_XINCREF(result);
 	return result;
 }
diff --git a/Python/bltinmodule.c b/Python/bltinmodule.c
index 05f6a81..b86e3fb 100644
--- a/Python/bltinmodule.c
+++ b/Python/bltinmodule.c
@@ -1494,14 +1494,14 @@ Precision may be negative.");
 static PyObject *
 builtin_sorted(PyObject *self, PyObject *args, PyObject *kwds)
 {
-	PyObject *newlist, *v, *seq, *compare=NULL, *keyfunc=NULL, *newargs;
+	PyObject *newlist, *v, *seq, *keyfunc=NULL, *newargs;
 	PyObject *callable;
-	static char *kwlist[] = {"iterable", "cmp", "key", "reverse", 0};
+	static char *kwlist[] = {"iterable", "key", "reverse", 0};
 	int reverse;
 
-	/* args 1-4 should match listsort in Objects/listobject.c */
-	if (!PyArg_ParseTupleAndKeywords(args, kwds, "O|OOi:sorted",
-		kwlist, &seq, &compare, &keyfunc, &reverse))
+	/* args 1-3 should match listsort in Objects/listobject.c */
+	if (!PyArg_ParseTupleAndKeywords(args, kwds, "O|Oi:sorted",
+		kwlist, &seq, &keyfunc, &reverse))
 		return NULL;
 
 	newlist = PySequence_List(seq);
@@ -1533,7 +1533,7 @@ builtin_sorted(PyObject *self, PyObject *args, PyObject *kwds)
 }
 
 PyDoc_STRVAR(sorted_doc,
-"sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted list");
+"sorted(iterable, key=None, reverse=False) --> new sorted list");
 
 static PyObject *
 builtin_vars(PyObject *self, PyObject *args)