[Finn Bock]
Changing the type of a type? Yuck!
No, it temporarily changes the type of the single list being sorted, like so, where "self" is a pointer to a PyListObject (which is a list, not a list *type* object): self->ob_type = &immutable_list_type; err = samplesortslice(self->ob_item, self->ob_item + self->ob_size, compare); self->ob_type = &PyList_Type; immutable_list_type is "just like" PyList_Type, except that the slots for mutating methods point to a function that raises a TypeError. Before this drastic step came years of increasingly ugly hacks trying to stop core dumps when people mutated a list during the sort. Python's sort is very complex, and lots of pointers are tucked away -- having the size of the array, or its position in memory, or the set of objects it contains, change as a side effect of doing a compare, would be difficult and expensive to recover from -- and by "difficult" read "nobody ever managed to get it right before this" <0.5 wink>.
I might very likely be reading the CPython sources wrongly, but it seems this trick will cause an BadInternalCall if some other C extension are trying to modify a list while it is freezed by the type switching trick. I imagine this would happen if the extension called:
PyList_SetItem(myList, 0, aValue);
Well, in CPython it's not "legal" for any other thread to use the C API while the sort is in progress, because the thread doing the sort holds the global interpreter lock for the duration. So this could happen "legally" only if a comparison function called by the sort called out to a C extension attempting to mutate the list. In that case, fine, it *is* a bad call: mutation is not allowed during list sorting, so they deserve whatever they get -- and far better a "bad internal call" than a core dump. If the immutable_list_type were used more generally, it would require more general support (but I see Thomas already talked about that -- thanks).