Raymond Hettinger <rhettinger@users.sourceforge.net> added the comment:
> That result is surprising though -- I thought the concept was
> manipulate the key and value arrays at the same time instead of just
> the keys

If the "key" parameter was not used, then the values pointer is a null pointer.  Each time elements must be moved, the code needs to check if the values pointer is NULL.  In other words, the overhead is one conditional branch per move or group of moves (we only have to check once for memmove()).

Since the branch will always be the same throughout any given call to sort(), CPU branch prediction is effective making the branches fairly inexpensive.

> -- did you do more than this, perhaps changing the logic or
> pattern of comparisons?

In the original version of the patch, I tried hard to avoid unrelated changes.  

In the new version, I made many small not-strictly-related optimizations.  However, I have not changed the order in which comparisons occur.

> Why did the variable names change, pa/pb to ssa/ssb, etc.?

I took "pa" to mean "pointer to array A", but it's now a sortslice structure instead of a pointer.

> comment lines are rewrapped

The comment rewrapping aren't completely spurious.  The comments really have changed and in some cases the constraints on the inputs to a function have changed slightly.

For what it's worth, my methodology when working on this patch went like this:
1) Make an improvement
2) Measure the performance relative to the previous reference point
3) If it was a statistically significant an improvement, commit the change to my local DVCS
4) Goto 1

I can upload the patch to Rietveld to facilitate review.

If I can get Rietveld to show each of my local commits, would it be helpful to see the patch in incremental pieces?