Python — Efficiency of sorting by multiple keys

Two simpler sorts can be faster than one more complex sort

Here are benchmarks with a few more versions:

At length = 10,000 elements, multikey still beats multisort:

0.023 seconds  multisort                 (no previous result)
 0.032 seconds  multisort_tupled          (same as previous result)
 0.027 seconds  multisort_tupled_gc_off   (same as previous result)
 0.015 seconds  multisort_inplaced        (same as previous result)
 0.020 seconds  multikey                  (same as previous result)
 0.020 seconds  multikey_gc_off           (same as previous result)

At length = 100,000, it already fell a bit behind:

0.300 seconds  multisort                 (no previous result)
 0.509 seconds  multisort_tupled          (same as previous result)
 0.442 seconds  multisort_tupled_gc_off   (same as previous result)
 0.237 seconds  multisort_inplaced        (same as previous result)
 0.349 seconds  multikey                  (same as previous result)
 0.372 seconds  multikey_gc_off           (same as previous result)

At length = 2,000,000, it's twice as slow:

3.902 seconds  multisort                 (no previous result)
 7.004 seconds  multisort_tupled          (same as previous result)
 6.433 seconds  multisort_tupled_gc_off   (same as previous result)
 3.745 seconds  multisort_inplaced        (same as previous result)
 7.944 seconds  multikey…