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.
Non-Comparison Sorts and Python's sort() is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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 sortingCounting 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)Stable Counting Sort with Cumulative Counts
For a stable counting sort (important when sorting objects by a key), compute cumulative counts so that cum[v] gives the starting position of value v in the output. Scan the input array from right to left, placing each element at position cum[key] - 1 and decrementing that position. This produces a stable sort — elements with the same key appear in their original relative order.
def counting_sort_stable(arr, k):
count = [0] * k
for n in arr: count[n] += 1
# Cumulative counts: count[v] = first position for value v
for i in range(1, k): count[i] += count[i-1]
output = [0] * len(arr)
# Fill from right to maintain stability
for n in reversed(arr):
count[n] -= 1
output[count[n]] = n
return output
print(counting_sort_stable([4,2,2,8,3,3,1], 9))
# [1, 2, 2, 3, 3, 4, 8]Radix Sort: Sort Digit by Digit
Radix sort sorts integers digit by digit, from the least significant digit (LSD) to the most significant (MSD), using a stable sort (like counting sort) at each digit position. After d passes (one per digit), the array is fully sorted. Time complexity: O(d × (n + k)) where d = number of digits and k = base (usually 10). For n integers bounded by W, d = log_k(W), giving O(n log_k(W)) total.
def radix_sort(arr):
if not arr: return []
max_val = max(arr)
exp = 1 # current digit position (1, 10, 100, ...)
while max_val // exp > 0:
arr = 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 n_ in arr: count[(n_ // exp) % 10] += 1
for i in range(1, 10): count[i] += count[i-1]
for n_ in reversed(arr):
d = (n_ // exp) % 10
count[d] -= 1
output[count[d]] = n_
return output
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]Bucket Sort: Distribute Into Buckets
Bucket sort distributes elements into a fixed number of buckets based on value range, sorts each bucket (with insertion sort for small buckets), and concatenates. For uniformly distributed data in [0, 1), n buckets gives O(n) average time. Time: O(n + k) average, O(n²) worst case (all elements in one bucket). Most useful when the data distribution is known and approximately uniform.
def bucket_sort(arr):
if not arr: return []
n = len(arr)
min_v, max_v = min(arr), max(arr)
if min_v == max_v: return arr[:]
buckets = [[] for _ in range(n)]
# Map each value to a bucket index
for v in arr:
idx = int((v - min_v) / (max_v - min_v + 1e-9) * n)
idx = min(idx, n - 1)
buckets[idx].append(v)
result = []
for bucket in buckets:
bucket.sort() # insertion sort for small buckets
result.extend(bucket)
return result
print(bucket_sort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21]))
# sorted listPython's Timsort Under the Hood
Python's sorted() and list.sort() use Timsort, designed by Tim Peters in 2002. Timsort is a hybrid of merge sort and insertion sort. It scans for 'natural runs' (already-sorted subsequences) and uses insertion sort to build runs up to 64 elements. It then merges runs using merge sort with several optimisations: galloping (skipping elements in bulk when one run is dominant) and run-length stacking.
# Timsort properties:
# - Stable
# - O(n log n) worst case
# - O(n) best case (data already sorted)
# - O(n) auxiliary space
# - Highly optimised for real-world data with runs
import time
# Nearly sorted data: Timsort is extremely fast
nearly_sorted = list(range(10000))
nearly_sorted[-1] = 0 # one mis-placed element
t = time.perf_counter()
not_used = sorted(nearly_sorted)
elapsed = time.perf_counter() - t
print(f'Timsort on nearly-sorted n=10000: {elapsed*1000:.3f} ms')Python's sort() vs sorted(): Key Differences
list.sort() sorts in-place, returns None, and only works on lists. sorted(iterable) works on any iterable (tuples, generators, dicts) and returns a new list. Both accept key and reverse parameters. A common bug: assigning the return of lst.sort() to a variable and wondering why it is None. Always use sorted() when you need the sorted version and want to keep the original.
nums = [3, 1, 4, 1, 5, 9]
# in-place: returns None
result = nums.sort()
print(result) # None (common bug!)
print(nums) # [1, 1, 3, 4, 5, 9] (modified)
nums2 = [3, 1, 4, 1, 5, 9]
# out-of-place: returns new list
result2 = sorted(nums2)
print(result2) # [1, 1, 3, 4, 5, 9]
print(nums2) # [3, 1, 4, 1, 5, 9] (unchanged)Custom Sort Keys in Interviews
Python's sort accepts a key function evaluated once per element (unlike C's comparator called for every pair). Common interview sort keys: len for string length, lambda x: -x for descending, lambda x: (x[1], x[0]) for multi-key sort, and str.lower for case-insensitive. Python's sort is guaranteed stable, so multi-key sorts work correctly.
# Sort by length, then alphabetically
words = ['banana', 'fig', 'apple', 'date', 'kiwi']
print(sorted(words, key=lambda w: (len(w), w)))
# ['fig', 'date', 'kiwi', 'apple', 'banana']
# Sort integers as strings (largest concatenation first)
nums = [3, 30, 34, 5, 9]
print(sorted(map(str, nums), key=lambda a: a*10, reverse=True))
# ['9', '5', '34', '3', '30'] => '9534330'
# Descending sort
print(sorted([3,1,4,1,5], reverse=True)) # [5,4,3,1,1]When to Use Each Sort in Interviews
Choose the right sort for the context:
- Use Python's sorted()/list.sort(): default for all interview problems — Timsort is optimal
- Counting sort: when values are bounded small integers (0 to k, k small)
- Radix sort: when sorting many integers with known bit-width or digit count
- Bucket sort: when data is uniformly distributed floats in a known range
- Implement merge sort: when asked to code a stable O(n log n) sort from scratch
# Problem: sort array of 0s, 1s, 2s efficiently
# Counting sort: O(n), O(1) space (k=3 is tiny)
def sort_012(arr):
count = [0, 0, 0]
for n in arr:
count[n] += 1
i = 0
for val in range(3):
for _ in range(count[val]):
arr[i] = val; i += 1
arr = [2, 0, 2, 1, 1, 0]
sort_012(arr)
print(arr) # [0, 0, 1, 1, 2, 2]Sort Without Sort: Top-K with a Heap
Many interview problems ask for 'sort-like' results without requiring a full sort. Finding the top-k elements: a min-heap of size k runs in O(n log k) — faster than O(n log n) when k << n. Finding the kth largest: quickselect is O(n) average. Finding the median: two-heap approach is O(log n) per insertion. These partial-sort approaches are worth knowing as faster alternatives to full sorting.
import heapq
# Top-k with heap: O(n log k)
def top_k(nums, k):
return heapq.nlargest(k, nums) # uses heap of size k internally
print(top_k([3,2,1,5,6,4], 2)) # [6, 5]
# kth largest: quickselect O(n) average
import random
def kth_largest(nums, k):
def _select(lo, hi, target):
if lo >= hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]; i = lo - 1
for j in range(lo, hi):
if nums[j] >= pivot: i+=1; nums[i],nums[j]=nums[j],nums[i]
nums[i+1],nums[hi]=nums[hi],nums[i+1]
p = i + 1
if p == target: return nums[p]
return _select(lo, p-1, target) if target < p else _select(p+1, hi, target)
return _select(0, len(nums)-1, k-1)
print(kth_largest([3,2,1,5,6,4], 2)) # 5Sort Stability in Multi-Key Sorting
Stability enables correct multi-key sorting: sort by secondary key first (stably), then by primary key (stably). The secondary order is preserved for ties in the primary key. This technique is used in databases (ORDER BY col1, col2) and in radix sort (each digit pass must be stable for the overall algorithm to be correct). Python's sort is always stable, so this pattern works reliably.
data = [
('Alice', 'Math', 90),
('Bob', 'Science', 85),
('Carol', 'Math', 90),
('Dave', 'Science', 90),
]
# Sort by score DESC, then by subject ASC (for ties)
# Step 1: sort by subject (secondary)
data.sort(key=lambda x: x[1])
# Step 2: sort by score DESC (primary, stable)
data.sort(key=lambda x: x[2], reverse=True)
for row in data:
print(row)
# All score=90 rows: Math before Science (preserved from step 1)Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: comparison-based sorts are bounded below by O(n log n) — breaking this bound requires non-comparison information like bounded integers, counting sort achieves O(n + k) by tallying frequencies, radix sort processes digits with O(d × (n + k)) total, and bucket sort exploits uniform distribution for O(n) average, and Python's Timsort is the practical default — stable, O(n log n) worst case, O(n) best case, and faster than any hand-coded alternative for real data. Next up we master classic binary search.
Frequently asked questions
Is the “Non-Comparison Sorts and Python's sort()” lesson free?
Yes — the full text of “Non-Comparison Sorts and Python's sort()” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “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. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Non-Comparison Sorts and Python's sort()” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Bubble Sort and Insertion Sort
- Merge Sort: Divide, Sort, Merge
- Quick Sort and Pivot Selection
- Non-Comparison Sorts and Python's sort()