0Pricing
DSA Interview Prep · Lesson

Non-Comparison Sorts and Python's sort()

Explore counting sort and radix sort for integer arrays, and understand how Python's Timsort works under the hood for built-in sort calls.

The O(n log n) Lower Bound for Comparisons

Any sorting algorithm that determines order only through element comparisons requires at least Ω(n log n) comparisons in the worst case. This is proven by the decision tree argument: sorting n elements requires distinguishing between n! possible orderings. A binary decision tree (each node is a comparison) needs at least log₂(n!) ≈ n log₂(n) levels. To break this bound, we need additional information about the elements — such as them being bounded integers.

import math

for n in [5, 10, 100, 1000]:
    lower_bound = n * math.log2(n)
    factorial_log = sum(math.log2(i) for i in range(1, n+1))
    print(f'n={n}: n*log2(n)={lower_bound:.1f}, log2(n!)={factorial_log:.1f}')

# n log n is a tight bound on comparison-based sorting

Counting Sort: Sort by Frequency

Counting sort works by counting the frequency of each value, then reconstructing the sorted array from the counts. It requires knowing the range [0, k) of values in advance. Time complexity: O(n + k); space complexity: O(k). For small k relative to n (e.g., sorting ages 0-120 or single digits), counting sort beats all comparison sorts. For large k, the O(k) space cost makes it impractical.

def counting_sort(arr, k=None):
    if not arr: return []
    if k is None: k = max(arr) + 1
    count = [0] * k
    for n in arr:
        count[n] += 1
    result = []
    for val, freq in enumerate(count):
        result.extend([val] * freq)
    return result

arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr))  # [1, 2, 2, 3, 3, 4, 8]
# O(n + k) where k = 9 (max value + 1)

All lessons in this course

  1. Bubble Sort and Insertion Sort
  2. Merge Sort: Divide, Sort, Merge
  3. Quick Sort and Pivot Selection
  4. Non-Comparison Sorts and Python's sort()
← Back to DSA Interview Prep