Sorting Algorithms Cheat Sheet

Updated 2026-05-25

Sorting algorithms are fundamental procedures in computer science that rearrange elements in a collection according to a comparison operator. They form the backbone of data organization, enabling efficient searching, data analysis, and optimal algorithm performance across countless applications—from database indexing to machine learning pipelines. While the theoretical lower bound for comparison-based sorting is $\Omega(n \log n)$ , the real-world performance varies dramatically based on input characteristics, memory hierarchy, and implementation details — Python 3.11 replaced TimSort with the provably near-optimal PowerSort, DeepMind's AlphaDev discovered assembly-level improvements of up to 70% for small fixed-size arrays, and IPS⁴o outperforms all known in-place and out-of-place parallel comparison sorts, proving the field far from settled.

What This Cheat Sheet Covers

This topic spans 18 focused tables and 101 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.

Table 1: Core Comparison-Based SortsTable 2: Advanced Hybrid AlgorithmsTable 3: Non-Comparison SortsTable 4: Time Complexity AnalysisTable 5: Algorithm PropertiesTable 6: Pivot Selection StrategiesTable 7: Partitioning SchemesTable 8: Specialized Sorting AlgorithmsTable 9: Tree-Based SortsTable 10: Parallel and GPU SortsTable 11: External SortingTable 12: Stable In-Place SortsTable 13: Algorithm Selection GuidelinesTable 14: Optimization TechniquesTable 15: Sorting NetworksTable 16: Uncommon Specialized SortsTable 17: Algorithm Implementation DetailsTable 18: Inversions and Complexity Metrics

Table 1: Core Comparison-Based Sorts

The six foundational comparison-based algorithms every programmer should know. They differ sharply in stability, in-place memory use, and worst-case behavior — knowing when each one wins and when it collapses is the first layer of sorting mastery.

Algorithm	Example	Description
QuickSort	`pivot = arr[mid]` `partition(arr, pivot)` `quicksort(left, right)`	• Divide-and-conquer algorithm that selects a pivot and partitions array around it • average-case $O(n \log n)$ but degrades to $O(n^2)$ on poor pivot selection • fastest in practice for most random inputs; default basis for most production sort implementations.
MergeSort	`divide(arr) → [left, right]` `merge(sorted_left, sorted_right)`	• Stable divide-and-conquer sort with guaranteed $O(n \log n)$ time in all cases • requires $O(n)$ auxiliary space for merging • excels with sequential access patterns, making it cache-friendly for large external datasets.
HeapSort	`build_max_heap(arr)` `extract_max() → sorted`	• In-place sort using a binary max-heap structure • consistent $O(n \log n)$ time with $O(1)$ space; build-heap phase is $O(n)$ • not stable; slower than QuickSort in practice due to poor cache locality from non-sequential access.
InsertionSort	`for i in 1..n:` `shift arr[i] left while > prev`	• Builds sorted array one element at a time by shifting • $O(n^2)$ worst case but $O(n)$ on nearly-sorted input • efficient for small arrays (n < 10–50) and used as base case in QuickSort, MergeSort, and TimSort.

Table 1: Core Comparison-Based Sorts

Algorithm	Example	Description
QuickSort	`pivot = arr[mid]` `partition(arr, pivot)` `quicksort(left, right)`	• Divide-and-conquer algorithm that selects a pivot and partitions array around it • average-case $O(n \log n)$ but degrades to $O(n^2)$ on poor pivot selection • fastest in practice for most random inputs; default basis for most production sort implementations.
MergeSort	`divide(arr) → [left, right]` `merge(sorted_left, sorted_right)`	• Stable divide-and-conquer sort with guaranteed $O(n \log n)$ time in all cases • requires $O(n)$ auxiliary space for merging • excels with sequential access patterns, making it cache-friendly for large external datasets.
HeapSort	`build_max_heap(arr)` `extract_max() → sorted`	• In-place sort using a binary max-heap structure • consistent $O(n \log n)$ time with $O(1)$ space; build-heap phase is $O(n)$ • not stable; slower than QuickSort in practice due to poor cache locality from non-sequential access.
InsertionSort	`for i in 1..n:` `shift arr[i] left while > prev`	• Builds sorted array one element at a time by shifting • $O(n^2)$ worst case but $O(n)$ on nearly-sorted input • efficient for small arrays (n < 10–50) and used as base case in QuickSort, MergeSort, and TimSort.