> If the "key" parameter was not used, then the values pointer 
> is a null pointer. 
  . . .
> Since the branch will always be the same throughout any given 
> call to sort(), CPU branch prediction is effective making the
> branches fairly inexpensive.

I see how the branch can be optimized away but not how it gets cheaper than when there was no branch at all (and no lo.keys and lo.values extra layer of direction).  How did it get *faster* than the original (in the case with no key-function)?

>> 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.

That makes sense.

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

At this point, it may be best for me to read the patch as-is.  Unfortunately, it's a big patch and will likely take a lot of time to read in detail.

Is there any chance you can persuade Uncle Timmy to review this?  This is all his code and he's likely to have some good insights.

Also, is there anyone else who is knowledgeable about Python on less common platforms?  ISTM part of the optimization is dependent on the branch-prediction and other nuances that vary from environment to environment.  That being said, doing fewer memory allocations is always a win.