### sort函数的具体排序算法 Python内置`list.sort()`方法以及`sorted()`函数采用了一种称为内省式排序（Introspective Sort, 或简称 Introsort）的混合排序策略[^1]。这种排序方式结合了多种经典排序算法的优点，在不同情况下切换不同的排序机制来优化性能。 #### 内省式排序的工作原理 内省式排序主要基于快速排序，这是一种高效的分治法排序技术。然而为了防止最坏情况的发生——即当数据已经接近有序时可能导致时间复杂度退化至O(n²)，一旦检测到递归调用层数超过了设定阈值（通常取为待排序数组长度对数），便会转换成堆排序继续处理剩余部分[^2]。 此外，在处理较小规模的数据集时，由于插入排序对于几乎已排序列表具有更好的局部性表现且常数因子较低，因此会进一步应用此简单而有效的排序手段作为补充措施之一。 通过上述三种排序方法的有效融合，使得 Python 的 `sort` 函数能够在大多数实际应用场景下提供稳定且高性能的表现。 ```python def introsort(arr): max_depth = (len(arr).bit_length() - 1) * 2 def sort_part(start, end, depth_limit): while end - start > 0: if depth_limit == 0: heapify_and_sort(arr, start, end) break pivot_index = partition(arr, start, end) # Recursively sort the smaller part and use insertion sort for small partitions if pivot_index - start < end - pivot_index: sort_part(start, pivot_index - 1, depth_limit - 1) start = pivot_index + 1 else: sort_part(pivot_index + 1, end, depth_limit - 1 if end - start <= INSERTION_SORT_THRESHOLD: insertionsort(arr[start:end+1]) break sort_part(0, len(arr)-1, max_depth) INSERTION_SORT_THRESHOLD = 16 def insertionsort(subarray): for i in range(1, len(subarray)): key_item = subarray[i] j = i - 1 while j >= 0 and subarray[j] > key_item: subarray[j + 1] = subarray[j] j -= 1 subarray[j + 1] = key_item ```