Sorting Algorithms Cheat Sheet
Compares common sorting algorithms by time and space complexity and stability, with runnable merge sort and quicksort implementations.
2 PagesIntermediateMar 22, 2026
Algorithm Comparison
Time complexity, space complexity, and stability at a glance.
- Bubble Sort- O(n^2) time, O(1) space, stable; repeatedly swaps adjacent out-of-order elements
- Insertion Sort- O(n^2) worst case but O(n) on nearly-sorted data, O(1) space, stable; good for small or almost-sorted arrays
- Selection Sort- O(n^2) time, O(1) space, not stable; repeatedly selects the minimum remaining element
- Merge Sort- O(n log n) time guaranteed, O(n) space, stable; divide-and-conquer, good for linked lists and external sorting
- Quicksort- O(n log n) average, O(n^2) worst case, O(log n) space, not stable; fast in practice due to cache locality
- Heapsort- O(n log n) time guaranteed, O(1) space, not stable; builds a heap then repeatedly extracts the max
Merge Sort
Classic divide-and-conquer sort with guaranteed O(n log n).
python
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]: result.append(left[i]); i += 1 else: result.append(right[j]); j += 1 result.extend(left[i:]) result.extend(right[j:]) return result
Quicksort
Fast average-case sort using a pivot and partitioning.
python
def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] mid = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quick_sort(left) + mid + quick_sort(right)
Using Built-in Sort
Python's Timsort with custom keys.
python
# Python's sort is Timsort (hybrid merge/insertion sort),# O(n log n) worst case, and stablenums = [5, 2, 8, 1]sorted(nums) # returns new list, ascendingnums.sort(reverse=True) # in-place, descending# Sorting with a custom keywords = ["banana", "kiwi", "apple"]sorted(words, key=len) # by length: ['kiwi', 'apple', 'banana']sorted(words, key=lambda w: w[::-1]) # by reversed string
Counting Sort
Non-comparison sort that runs in O(n + k) time for integers within a known small range k, faster than any comparison sort.
python
def counting_sort(arr, max_val): counts = [0] * (max_val + 1) for x in arr: counts[x] += 1 for i in range(1, len(counts)): counts[i] += counts[i - 1] # prefix sums -> final positions output = [0] * len(arr) for x in reversed(arr): # reversed traversal keeps it stable counts[x] -= 1 output[counts[x]] = x return outputcounting_sort([4, 2, 2, 8, 3, 3, 1], 8) # => [1, 2, 2, 3, 3, 4, 8]
Radix Sort (LSD)
Sorts integers digit by digit using a stable counting sort as a subroutine; O(d * (n + k)) for d digits.
python
def radix_sort(arr): if not arr: return arr max_val = max(arr) exp = 1 result = arr[:] while max_val // exp > 0: buckets = [[] for _ in range(10)] for x in result: buckets[(x // exp) % 10].append(x) result = [x for bucket in buckets for x in bucket] exp *= 10 return resultradix_sort([170, 45, 75, 90, 802, 24, 2, 66])
Quickselect (Kth Smallest)
Finds the kth smallest element in expected O(n) using quicksort's partitioning without fully sorting the array.
python
import randomdef quickselect(arr, k): pivot = random.choice(arr) less = [x for x in arr if x < pivot] equal = [x for x in arr if x == pivot] greater = [x for x in arr if x > pivot] if k < len(less): return quickselect(less, k) elif k < len(less) + len(equal): return pivot else: return quickselect(greater, k - len(less) - len(equal))quickselect([7, 10, 4, 3, 20, 15], 2) # => 7 (0-indexed 3rd smallest)
Dutch National Flag Partitioning
Three-way partitioning around a pivot in a single O(n) pass, which makes quicksort O(n) instead of O(n log n) on arrays with many duplicates.
python
def dutch_flag_partition(arr, pivot): low, mid, high = 0, 0, len(arr) - 1 while mid <= high: if arr[mid] < pivot: arr[low], arr[mid] = arr[mid], arr[low] low += 1 mid += 1 elif arr[mid] == pivot: mid += 1 else: arr[mid], arr[high] = arr[high], arr[mid] high -= 1 return arr # elements < pivot, then == pivot, then > pivot
Real-World Sorting Considerations
Details that separate textbook sorts from production-grade sorting.
- Timsort's runs- Python/Java's built-in sort detects existing ascending/descending "runs" in the data and merges them, giving O(n) best case on partially sorted input
- Minrun heuristic- Timsort switches to insertion sort for runs below a computed minrun length (typically 32-64), since insertion sort beats merge sort on tiny arrays
- Introsort- C++'s std::sort starts with quicksort, falls back to heapsort if recursion depth exceeds a threshold (avoiding O(n^2) worst case), and uses insertion sort for small partitions
- External sorting- Sorts data too large for memory by sorting chunks on disk, then k-way merging them; used by database engines for ORDER BY on huge tables
- Stability's practical cost- Stable sorts preserve equal-key ordering, which matters when sorting by one key after already sorting by another (e.g. sort by last name, then by department)
- Parallel sorting- Merge sort parallelizes naturally by sorting sub-arrays on separate threads/cores and merging results, unlike in-place quicksort which has more data dependencies
Pro Tip
Reach for the language's built-in sort (Timsort in Python, Collections.sort in Java, introsort in C++'s std::sort) instead of hand-rolling one — they're heavily optimized and, for Python/Java, stable by default.
Was this cheat sheet helpful?
Explore Topics
#SortingAlgorithms#SortingAlgorithmsCheatSheet#Programming#Intermediate#AlgorithmComparison#MergeSort#Quicksort#UsingBuiltInSort#Algorithms#Git#CheatSheet#SkillVeris
