In-depth comparison of the performance of the top ten sorting algorithms

def bubble_sort(arr):    n = len(arr)    for i in range(n):        swapped = False        for j in range(0, n - i - 1):            if arr[j] > arr[j + 1]:                arr[j], arr[j + 1] = arr[j + 1], arr[j]                swapped = True        if not swapped:  # 若本轮无交换，说明已有序            break    return arr

def selection_sort(arr):    n = len(arr)    for i in range(n):        min_idx = i        for j in range(i + 1, n):            if arr[j] < arr[min_idx]:                min_idx = j        arr[i], arr[min_idx] = arr[min_idx], arr[i]    return arr

def insertion_sort(arr):    for i in range(1, len(arr)):        key = arr[i]        j = i - 1        while j >= 0 and arr[j] > key:            arr[j + 1] = arr[j]            j -= 1        arr[j + 1] = key    return arr

def shell_sort(arr):    n = len(arr)    gap = n // 2    while gap > 0:        for i in range(gap, n):            temp = arr[i]            j = i            while j >= gap and arr[j - gap] > temp:                arr[j] = arr[j - gap]                j -= gap            arr[j] = temp        gap //= 2    return arr

def quick_sort(arr, low=0, high=None):    if high is None:        high = len(arr) - 1    if low < high:        pivot_idx = partition(arr, low, high)        quick_sort(arr, low, pivot_idx - 1)        quick_sort(arr, pivot_idx + 1, high)    return arr def partition(arr, low, high):    pivot = arr[high]  # 选择最后一个元素作为基准    i = low - 1    for j in range(low, high):        if arr[j] <= pivot:            i += 1            arr[i], arr[j] = arr[j], arr[i]    arr[i + 1], arr[high] = arr[high], arr[i + 1]    return i + 1

def merge_sort(arr):    if len(arr) <= 1:        return arr    mid = len(arr) // 2    left = merge_sort(arr[:mid])    right = merge_sort(arr[mid:])    return merge(left, right) def merge(left, right):    result = []    i = j = 0    while i < len(left) and j < len(right):        if left[i] <= right[j]: # <= ensure stability            result.append(left[i])            i += 1        else:            result.append(right[j])            j += 1    result.extend(left[i:])    result.extend(right[j:])    return result

def heap_sort(arr):    n = len(arr)     # 构建最大堆    for i in range(n // 2 - 1, -1, -1):        heapify(arr, n, i)     # 逐个提取堆顶元素    for i in range(n - 1, 0, -1):        arr[0], arr[i] = arr[i], arr[0]        heapify(arr, i, 0)    return arr def heapify(arr, n, i):    largest = i    left = 2 * i + 1    right = 2 * i + 2    if left < n and arr[left] > arr[largest]:        largest = left    if right < n and arr[right] > arr[largest]:        largest = right    if largest != i:        arr[i], arr[largest] = arr[largest], arr[i]        heapify(arr, n, largest)

def counting_sort(arr):    if not arr:        return arr    max_val = max(arr)    min_val = min(arr)    range_val = max_val - min_val + 1     count = [0] * range_val     for num in arr:     # Cumulative count     # Traverse from back to front to maintain stability     return output ## 9. Bucket Sort **Brief description of the principle:** Bucket sorting distributes data into several "buckets", each bucket is sorted independently (usually using insertion sort or other sorting algorithms), and finally the results of all buckets are spliced ​​together. Bucket sort is extremely efficient when the data is evenly distributed. **Complexity Analysis:**- Best time complexity: O(n + k) (data is uniformly distributed, k is the number of buckets)- Worst time complexity: O(n²) (all data falls into the same bucket)- Average time complexity: O(n + n²/k + k), O(n) when k ≈ n- Space complexity: O(n + k)- Stability: **Stable** (depends on the bucket sorting algorithm) ```pythondef bucket_sort(arr, bucket_count=10):    if not arr:        return arr    min_val, max_val = min(arr), max(arr)    bucket_range = (max_val - min_val) / bucket_count + 1     buckets = [[] for _ in range(bucket_count)]     for num in arr:        idx = int((num - min_val) / bucket_range)        buckets[idx].append(num)     result = []    for bucket in buckets:        result.extend(insertion_sort(bucket))  # 桶内使用插入排序    return result

def radix_sort(arr):    if not arr:        return arr    max_val = max(arr)    exp = 1    while max_val // exp > 0:        counting_sort_by_digit(arr, exp)        exp *= 10    return arr def counting_sort_by_digit(arr, exp):    n = len(arr)    output = [0] * n    count = [0] * 10     for num in arr:     for i in range(1, 10):     for i in range(n - 1, -1, -1):     for i in range(n): ## Full comparison table | Sorting algorithm | Best time | Average time | Worst time | Space complexity | Stability ||---------|---------|---------|---------|----------|--------|| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Stable || Selection sort | O(n²) | O(n²) | O(n²) | O(1) | Unstable || Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Stable || Hill sort | O(n log n) | O(n^1.3) | O(n²) | O(1) | Unstable || Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | Unstable || Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Stable || Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Unstable || Counting sort | O(n+k) | O(n+k) | O(n+k) | O(n+k) | Stable || Bucket sort | O(n+k) | O(n+k) | O(n²) | O(n+k) | Stable || Radix sort | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | Stable | > Note: k is the data range or the number of buckets, and d is the maximum number of digits. ## Actual application scenario analysis **Small size data (n < 50):** Insertion sort is the best choice. The constant factor is small and extremely efficient for nearly ordered data. **Medium-Scale General Purpose Sort:** Quicksort is the fastest comparison sorting algorithm in most scenarios, with a small constant factor in the average case. **Stable sort required:** Merge sort is an O(n log n) algorithm that is stable and has predictable performance. Stability is crucial in scenarios where the original order of equal elements needs to be preserved (such as multi-key sorting). **Memory limited:** Heap sort requires only O(1) extra space, suitable for embedded systems with tight memory. **Integer sorting with limited data range:** Counting sort or radix sort can achieve linear time complexity that far exceeds the O(n log n) theoretical lower bound of comparison sort. **Large-scale external sorting:** Merge sort is a natural fit for external sorting because its sequential access pattern lends itself well to disk I/O. **Floating point sorting with uniform data distribution:** Bucket sorting can achieve near-linear sorting efficiency. ## The underlying implementation of sorting in each language’s standard library ### Python — Timsort Python's built-in `sort()` and `sorted()` use the **Timsort** algorithm, designed by Tim Peters in 2002. Timsort is a hybrid sorting algorithm that combines the advantages of merge sort and insertion sort: - First identify an ordered subsequence in the data (called a "run") The time complexity of Timsort is O(n log n), and it performs particularly well on partially sorted data, and can reach O(n) in the best case. ### C — qsort The C standard library's `qsort()` is usually implemented based on quick sort, but the specific implementation varies between compilers. glibc's implementation uses merge sort (when there is enough memory) or quick sort (when there is not enough memory), and uses insertion sort optimization on small arrays. MSVC's implementation uses introspective sorting (Introsort), combining quick sort, heap sort, and insertion sort. ### Java — Dual-Pivot Quicksort and Timsort Java uses **Dual-Pivot Quicksort** (dual-pivot quicksort, designed by Vladimir Yaroslavskiy) for arrays of primitive types, choosing two pivots to divide the array into three parts, which is faster in practice than classic quicksort. For object arrays, Java uses **Timsort** to ensure the stability of sorting. ### C++ — Introsort C++ STL's `std::sort` usually uses **Introsort** (introspective sort), proposed by David Musser in 1997. It starts with quick sort, switches to heap sort when the recursion depth exceeds 2×log₂(n) to guarantee the worst case of O(n log n), and uses insertion sort for small arrays. ### Go — Pattern-Defeating Quicksort (pdqsort) The Go language standard library uses **pdqsort**, which is a modern hybrid sorting algorithm that is close to the performance of quick sort on random data and can efficiently handle data in special patterns such as sorted, reverse order, and large number of repetitions. ## Summary and selection suggestions There is no absolute "best" sorting algorithm, only the one that is most suitable for a specific scenario. Here is a brief decision-making guide: 1. **When in doubt, use the language standard library**: The sorting implementation of the modern language standard library has been carefully optimized and is the best choice for most scenarios. Understanding these algorithms not only helps to choose appropriate sorting solutions, but also cultivates the thinking ability to analyze problems and design algorithms. The theoretical lower bound of comparative sorting is O(n log n), but non-comparative sorting can break through this limit under certain conditions - this idea itself is an exquisite example of "breaking conventional constraints" in algorithm design.