Just for the record, I wanted to highlight how little room there is for optimization here.  The sort wrapper is *very* thin:

sortwrapper_richcompare(sortwrapperobject *a, sortwrapperobject *b, int op)
{
    if (!PyObject_TypeCheck(b, &PySortWrapper_Type)) {
        PyErr_SetString(PyExc_TypeError,
            "expected a sortwrapperobject");
        return NULL;
    }
    return PyObject_RichCompare(a->key, b->key, op);
}

When a key function is defined, this is all you can possibly shave off the time for a comparison.  When a key function is not defined, there was no overhead at all.

With the patch, we're relying on branch prediction to minimize the cost to the regular case and adding a little indirection in the form of lo variables becoming lo.keys, etc.  And the number of memmoves is doubled.

To me, the main advantage of the patch is that it saves a little memory for each key:

   typedef struct {
       PyObject_HEAD
       PyObject *key;
       PyObject *value;
   } sortwrapperobject;

Just wanted to post this so there weren't any illusions about the patch being a big win.