Python3中key=len与key=lambda x: (len(x), x)的排序差异及sorted函数内部实现探究

Hey there! Let's break down your question into two clear parts: why those two sorted results differ, and how the sorted(key=...) mechanism works under the hood.

Why the Two Sort Results Are Different #

Let's start with the core difference between your two key functions:

1. Using key=len:
   When you pass len as the key, Python’s sorted only uses the length of each string to determine order. For elements with the same length, since sorted is a stable sort, it preserves their original relative order from the input list.
   In your test list, the length-4 strings appear in the order 'abcd', 'dbca', 'bcda' — so after sorting by length alone, they stay in that exact order. Similarly, the length-6 strings 'ssdfgh' and 'abcdef' keep their original order because their lengths are equal.

2. Using key=lambda x: (len(x), x):
   Here, you’re passing a tuple as the key. When comparing tuples, Python checks elements from left to right: first compare the lengths, and if those are equal, it then compares the strings themselves using lexicographical (dictionary) order.
   For the length-4 strings: 'abcd' < 'bcda' < 'dbca' lex order, so they get reordered to this sequence. For the length-6 strings: 'abcdef' comes before 'ssdfgh' lex order, so their positions swap compared to the first sort result.

That’s exactly why your test1 and test2 have different orderings for elements of the same length.

How sorted(key=...) Works Internally #

Python’s sorted function uses Timsort — a hybrid, stable sorting algorithm that combines the best parts of merge sort and insertion sort. Here’s a step-by-step breakdown of how the key parameter is handled:

1. Precompute key-value pairs:
   First, sorted iterates over your input list and creates a temporary list of tuples, where each tuple is (computed_key, original_element). For example:

   • With key=len, the temp list starts as [(2, 'aa'), (2, 'bb'), (2, 'cc'), (4, 'abcd'), ...]
   • With the lambda key, it becomes [(2, 'aa'), (2, 'bb'), (2, 'cc'), (4, 'abcd'), (4, 'dbca'), (4, 'bcda'), ...]

2. Sort using the tuples:
   Timsort then sorts this temporary list. When comparing two tuples, it first checks the first element (the key). If those are equal, it moves to the next element in the tuple (for your lambda case, that’s the string itself). For the key=len case, since the tuples only have a length as the key, equal keys mean the original order is preserved (stable sort behavior).

3. Extract the original elements:
   Once the temporary list is sorted, sorted strips out the key values and returns a list of just the original elements in their new sorted order.

It’s worth noting that precomputing the keys once (instead of recalculating them during each comparison) makes the sort efficient — this is why using a key is faster than a custom cmp function (which was deprecated in Python 3).

内容的提问来源于stack exchange，提问作者su00