Select comparison function for sorting based on type information
Bug
I don't know anything about the python interpreter, but this if statement:

if (keys_are_in_tuples &amp;&amp;
    (lo.keys[i]-&gt;ob_type != &amp;PyTuple_Type || Py_SIZE(lo.keys[0]) == 0)){


should be:
if (keys_are_in_tuples &amp;&amp;
    (lo.keys[i]-&gt;ob_type != &amp;PyTuple_Type || Py_SIZE(lo.keys[i]) == 0)){

where keys[0] was changed to keys[i] in the size check.  Otherwise the size check will always be false, since Py_SIZE(lo.keys[0]) was already determined to be nonzero if keys_are_in_tuples is true.
Suggestion for simplification
If you created static inline functions like these:
static inline bool key_is_in_tuple(PyObject *obj)
{
    return obj-&gt;ob_type == &amp;PyTuple_Type &amp;&amp; Py_SIZE(obj) &gt; 0;
}

static inline PyTypeObject *get_key_type(PyObject *obj)
{
    return key_is_in_tuple(obj) ?
               PyTuple_GET_ITEM(obj,0)-&gt;ob_type :
               obj-&gt;ob_type);
}

Then your code would read easier:
/* Turn off type checking if all keys are same type,
 * by replacing PyObject_RichCompare with lo.keys[0]-&gt;ob_type-&gt;tp_richcompare,
 * and possibly also use optimized comparison functions if keys are strings or ints.
 */
/* Get information about the first element of the list */
int keys_are_in_tuples = key_is_in_tuple(lo.keys[0]);

PyTypeObject* key_type = get_key_type(lo.keys[0]);

int keys_are_all_same_type = 1;
int strings_are_latin = 1;
int ints_are_bounded = 1;

/* Test that the above bools hold for the entire list */
for (i=0; i&lt; saved_ob_size; i++) {

  if (keys_are_in_tuples &amp;&amp; !key_is_in_tuple(lo.keys[i]) {
    keys_are_in_tuples = 0;
    keys_are_all_same_type = 0;
    break;
  }

  if (get_key_type(lo.keys[i]) != key_type) {
      keys_are_all_same_type = 0;
      break;
  }
  // ...