Nine ways to put things in order — from the dead-simple to the surprisingly clever. Each one makes different trade-offs between speed, memory, and stability.
🟢 Beginner → AdvancedSorting means rearranging a collection of items into a specific order — usually ascending or descending by some value. That sounds trivial until you have a million items and need it done in under a second.
Here's why it matters: sorted data is searchable data. Binary search needs sorted input. Duplicate detection becomes trivial on sorted arrays. Database indexes are just sorted structures. If you're writing software, you're sorting things — even when you don't realize it.
Sorting is one of the oldest problems in computer science. Herman Hollerith built a sorting machine for the 1890 US Census that sorted punched cards into bins — essentially a mechanical radix sort. By the 1940s, John von Neumann had described the merge sort algorithm (one of the earliest divide-and-conquer methods ever written down). Tony Hoare invented Quick Sort in 1960 while trying to sort words for a machine translation project at Moscow State University. He called it "Quicksort" because it was... quick.
The study of sorting drove much of early algorithm analysis. Donald Knuth devoted an entire volume of The Art of Computer Programming (Volume 3, published 1973) to sorting and searching. It's fair to say that half of what we know about algorithm design came from people trying to sort things faster.
Sorting algorithms split into two families:
A stable sort preserves the relative order of equal elements. Picture sorting a class roster by grade. If two students both have a B+, a stable sort keeps them in whatever order they were in originally. Merge Sort is stable. Quick Sort isn't (without extra work). Stability matters when you're doing multi-key sorts — sort by name first, then by grade with a stable sort, and students with the same grade stay alphabetically ordered.
An in-place sort uses O(1) extra memory — it rearranges items within the original array rather than allocating a separate output buffer. Quick Sort is in-place. Merge Sort typically isn't (it needs an O(n) merge buffer). In-place is nice when memory is tight, but it often comes with trade-offs in stability or code complexity.
An adaptive sort runs faster on nearly-sorted input. Insertion Sort is naturally adaptive — O(n) on sorted data. A non-adaptive sort like Selection Sort always does O(n²) comparisons regardless. Tim Sort is adaptive by design: it detects pre-existing order and exploits it.
The concept of inversions — a pair of elements that are out of order — is how we quantify "how unsorted" an array is. A sorted array has 0 inversions. A reverse-sorted array of n elements has n(n-1)/2 inversions (the maximum). Insertion Sort does exactly one swap per inversion, which is why it's fast on nearly-sorted data.
Walk through the array, compare each pair of neighbors, swap them if they're out of order. Repeat until nothing swaps. The largest unsorted element "bubbles" to the end each pass — hence the name. It's the first sort most people learn, and the last one you'd use in production.
One useful optimization: if you complete a pass with zero swaps, the array is already sorted and you can stop early. This makes Bubble Sort O(n) on already-sorted input, though it's still abysmal on everything else. Each pass locks one more element into its final position at the end of the array, so the inner loop can shrink by one each time.
Edge case to watch: Bubble Sort handles arrays with many duplicates correctly — equal elements never swap, so it's stable by nature.
Scan the unsorted portion for the smallest element, swap it to the front. Move the boundary one step right, repeat. Simple, but does O(n²) comparisons no matter what — even on already-sorted input. The number of swaps is at most n-1, which is actually pretty good. If your bottleneck is writes (say, flash memory with limited write cycles), Selection Sort makes a bizarre amount of sense.
Stability warning: Selection Sort is not stable in its typical implementation. When you swap the minimum to the front, you might jump it over an equal element. You can make it stable by shifting elements instead of swapping, but then you lose the low-swap advantage.
Take each element and slide it left into its correct position among the already-sorted elements before it. Think about how you'd sort a hand of playing cards — you pick up one card at a time and slot it in where it belongs. That's Insertion Sort.
Fast on small or nearly-sorted arrays. The number of shifts equals the number of inversions in the input, so if the data is almost sorted, Insertion Sort is almost O(n). That's why Tim Sort uses it for short runs (typically under 32–64 elements). Worst case is still O(n²), but the constant factors are tiny and it has excellent cache locality because it only touches nearby elements.
Binary Insertion Sort: You can use binary search to find where each element should go (cutting the comparison count to O(n log n)), but you still need O(n²) shifts to move elements. So the comparison cost improves, but the total time stays O(n²). Useful when comparisons are expensive relative to moves.
Split the array in half, recursively sort each half, then merge the two sorted halves together. The merge step walks both halves simultaneously, picking the smaller element each time. Guaranteed O(n log n) always — best, average, and worst case. Stable. But it needs O(n) extra space for the merge buffer, which is its main downside.
How the merge step works in detail: You have two sorted arrays, left and right. Maintain a pointer into each. Compare the elements at both pointers, take the smaller one and advance that pointer. Repeat until one array is exhausted, then copy whatever remains from the other. This is O(n) for two halves that sum to n elements.
Recursion depth: The array splits in half each time, so the depth is log₂(n). Each level of recursion does O(n) total merge work. That gives O(n log n) total.
Natural Merge Sort: Instead of always splitting at the midpoint, detect natural runs (already-sorted subsequences) and merge those. Tim Sort is essentially this idea, polished to perfection.
Pick a pivot element (a value used to partition the array). Rearrange so everything smaller goes left, everything larger goes right — this rearrangement step is called partitioning. Recursively sort both sides. Average case is O(n log n) with small constants — it's typically the fastest comparison sort in practice. Worst case is O(n²) when pivots are badly chosen (every pivot is the minimum or maximum), but randomized pivot selection makes that astronomically unlikely.
Two common partition schemes:
i tracks where the next smaller element should go. Simpler but does more swaps on average.Three-way partitioning (Dutch National Flag): Partitions into three groups: less than pivot, equal to pivot, greater than pivot. Crucial for arrays with many duplicate values — without it, equal elements cause unnecessary recursive calls and the worst case becomes likely on arrays with few distinct values.
Build a max-heap from the array — a complete binary tree where every parent is ≥ its children. (Building the heap takes O(n) via a bottom-up heapify process, which is faster than inserting elements one by one.) Then repeatedly extract the max element and place it at the end. Each extraction takes O(log n), and you do it n times: O(n log n) total.
Guaranteed O(n log n) and in-place (O(1) extra space). So why isn't it the default? Poor cache locality. Heap operations jump around memory unpredictably, while Quick Sort and Merge Sort access memory more sequentially. In practice, Heap Sort is 2-3x slower than Quick Sort despite the same asymptotic complexity.
When Heap Sort wins: Systems where you need a guaranteed O(n log n) worst case with O(1) extra memory. The Linux kernel's sort() function uses a hybrid of Quick Sort and Heap Sort — it starts with Quick Sort, but falls back to Heap Sort if the recursion depth gets too deep (this hybrid is called Introsort).
Count how many times each value appears, then use those counts to place elements directly. Only works when you know the range of values and that range (call it k) isn't huge. Time is O(n + k). It's not comparison-based, so it can beat the O(n log n) barrier.
How it works step by step: (1) Find min and max values. (2) Create a count array of size max - min + 1, initialized to zeros. (3) Walk the input and increment the count for each value. (4) Walk the count array and output each value the appropriate number of times.
When to avoid it: If your values range from 1 to 10 million but you only have 100 elements, you're allocating 10 million counters for 100 items. The count array size depends on the value range, not the input size. For floating-point data, it doesn't work at all (you can't index into an array with 3.14).
Sort by individual digits, starting from the least significant digit (LSD). Use a stable sub-sort (usually Counting Sort) for each digit position. Time is O(d × (n + k)) where d is the number of digits and k is the base (radix — the number of possible values per digit, often 10 for decimal or 256 for bytes). Works great for integers, fixed-length strings, and IP addresses.
LSD vs MSD: LSD (Least Significant Digit first) is simpler and naturally stable. MSD (Most Significant Digit first) processes the most significant digit first and can short-circuit when groups are small, but it's more complex and requires careful handling.
Practical trick: Use base 256 (each byte is a "digit") for sorting 32-bit integers. Then d = 4 and each pass is fast. Four passes of Counting Sort on bytes sorts any 32-bit integer array in O(4 × (n + 256)) = O(n) time. This is genuinely faster than Quick Sort for large arrays of integers.
The real-world champion, invented by Tim Peters in 2002 for Python. Java adopted it in 2009 for Arrays.sort() on objects. Tim Sort finds naturally occurring sorted subsequences (called runs — contiguous sections that are already ascending or descending), extends short runs with Insertion Sort (using a minimum run size called minrun, typically 32-64), then merges runs using a strategy that minimizes comparisons.
It's O(n log n) worst case, O(n) on already-sorted data, and stable. The merging strategy uses a stack of pending runs and specific rules about when to merge (called the "merge invariant") that ensure good balance. It also uses a technique called galloping mode during merges — when one run is consistently winning the comparisons, it switches to exponential search to skip ahead faster.
Why it dominates: Real-world data is rarely random. Databases have partially sorted columns. Log files are timestamped. User lists are alphabetized. Tim Sort detects and exploits this existing order, running much faster than O(n log n) on typical data while never doing worse.
Pick an algorithm, hit Play, and watch how it rearranges the bars. Pay attention to which elements get compared (highlighted) versus which ones actually move.
sorted() is stable — use it.
sorted(), Java's Arrays.sort(), C++'s std::sort()) are battle-tested, optimized, and correct. Your hand-rolled Quick Sort probably has an off-by-one bug and definitely has worse cache behavior. Use the built-in sort and invest your time in the rest of the problem.
Here's the full picture. "Best" means already-sorted input (or near it). "Average" is random input. "Worst" is pathological input like reverse-sorted for Quick Sort.
| Algorithm | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |
| Radix Sort | O(d·(n+k)) | O(d·(n+k)) | O(d·(n+k)) | O(n + k) | Yes |
| Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes |
Here are the three most interview-relevant sorts: Merge Sort (stable, guaranteed O(n log n)), Quick Sort (fastest in practice), and Counting Sort (linear time, non-comparison).
def merge_sort(arr):
"""Divide the array in half, sort each half, merge them.
Time: O(n log n) always. Space: O(n) for merge buffer.
Stable: yes — equal elements keep their original order."""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # Sort the left half
right = merge_sort(arr[mid:]) # Sort the right half
# Merge two sorted halves by walking both simultaneously
result = []
i = j = 0
while i < len(left) and j < len(right):
# <= (not <) makes this stable — equal elements from left
# come first, preserving their original relative order
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# One side is exhausted; append whatever remains from the other
result.extend(left[i:])
result.extend(right[j:])
return result
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
// Stable: pick from left on ties
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
// Drain remaining elements
return result.concat(left.slice(i), right.slice(j));
}
import random
def quick_sort(arr, lo=0, hi=None):
"""In-place Quick Sort with randomized pivot.
Average O(n log n), worst O(n²) (extremely unlikely with random pivot).
Space: O(log n) for the recursion stack."""
if hi is None:
hi = len(arr) - 1
if lo >= hi:
return
# Randomize pivot to avoid O(n²) on sorted/reverse-sorted input
pivot_idx = random.randint(lo, hi)
arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
pivot = arr[hi]
# i tracks where the next smaller-than-pivot element should go
# Everything left of i is < pivot, everything from i to j is >= pivot
i = lo
for j in range(lo, hi):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[hi] = arr[hi], arr[i] # Place pivot in final position
quick_sort(arr, lo, i - 1) # Sort left of pivot
quick_sort(arr, i + 1, hi) # Sort right of pivot
def quick_sort_hoare(arr, lo=0, hi=None):
"""Hoare partition: two pointers walk inward from both ends.
Fewer swaps on average than Lomuto. Trickier to get right."""
if hi is None:
hi = len(arr) - 1
if lo >= hi:
return
pivot = arr[(lo + hi) // 2] # Median element as pivot
i, j = lo, hi
# Partition: elements <= pivot go left, elements >= pivot go right
while True:
while arr[i] < pivot:
i += 1
while arr[j] > pivot:
j -= 1
if i >= j:
break
arr[i], arr[j] = arr[j], arr[i]
i += 1
j -= 1
# Note: Hoare returns j, and the pivot isn't necessarily at j
quick_sort_hoare(arr, lo, j)
quick_sort_hoare(arr, j + 1, hi)
def counting_sort(arr):
"""Sort integers by counting occurrences. O(n + k) time,
where k = max(arr) - min(arr). Only works for discrete values
with a known, reasonable range."""
if not arr:
return arr
lo, hi = min(arr), max(arr)
# Count array covers the full value range
counts = [0] * (hi - lo + 1)
for val in arr:
counts[val - lo] += 1
# Rebuild the array from counts
result = []
for i, count in enumerate(counts):
result.extend([i + lo] * count)
return result
def insertion_sort(arr):
"""Sort by sliding each element left into its correct position.
O(n) best case (sorted input), O(n²) worst case.
Used by Tim Sort for small subarrays because of low overhead."""
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
# Shift elements right until we find key's spot
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
You're building a game leaderboard. Players have scores, usernames, and timestamps. You need to display the top 100 players, sorted by score (descending), with ties broken by who achieved the score first (ascending timestamp). This is a classic multi-key sort with stability requirements.
from dataclasses import dataclass
from datetime import datetime
@dataclass
class Player:
username: str
score: int
achieved_at: datetime # When they hit this score
# Sample data
players = [
Player("alice", 9500, datetime(2026, 3, 1, 10, 30)),
Player("bob", 9500, datetime(2026, 3, 1, 9, 15)), # Same score, earlier
Player("charlie", 8700, datetime(2026, 2, 28, 14, 0)),
Player("diana", 9800, datetime(2026, 3, 2, 11, 45)),
Player("eve", 8700, datetime(2026, 3, 1, 8, 0)), # Same score as charlie
]
# Multi-key sort: primary = score (descending), secondary = time (ascending)
# Python's sort is stable, so we can sort by secondary key first,
# then by primary key — the secondary ordering is preserved within ties.
#
# OR, more directly, use a tuple key:
leaderboard = sorted(
players,
key=lambda p: (-p.score, p.achieved_at) # Negate score for descending
)
# Display top players
for rank, player in enumerate(leaderboard, 1):
print(f"#{rank} {player.username}: {player.score} pts "
f"(achieved {player.achieved_at.strftime('%b %d, %H:%M')})")
# Output:
# #1 diana: 9800 pts (achieved Mar 02, 11:45)
# #2 bob: 9500 pts (achieved Mar 01, 09:15) ← bob before alice (earlier)
# #3 alice: 9500 pts (achieved Mar 01, 10:30)
# #4 charlie: 8700 pts (achieved Feb 28, 14:00) ← charlie before eve (earlier)
# #5 eve: 8700 pts (achieved Mar 01, 08:00)
Notice that bob and alice both have 9500 points, but bob ranks higher because he achieved the score earlier. Without a stable sort or explicit tiebreaker, their ordering would be unpredictable. The (-p.score, p.achieved_at) tuple key handles both sort dimensions in a single pass.
sorted(arr, key=lambda x: ...). In JS: arr.sort((a, b) => ...). The comparator should return a negative number if a comes first, positive if b comes first, zero if equal.
Start with the mediums — they test whether you can apply sorting as a tool, not whether you can implement it.