--- # === IDENTITY === id: software/patterns/sorting-algorithms/2026 canonical_question: "What are the sorting algorithms compared (time, space, stability, when to use)?" aliases: - "sorting algorithm comparison chart" - "which sorting algorithm should I use" - "quicksort vs mergesort vs heapsort" - "best sorting algorithm for my use case" - "time complexity of sorting algorithms" entity_type: software_reference domain: software > patterns > sorting algorithms region: global jurisdiction: global temporal_scope: 1959-2026 # === VERIFICATION === last_verified: 2026-02-24 confidence: 0.95 version: 1.0 first_published: 2026-02-24 # === TEMPORAL VALIDITY === temporal_validity: status: stable last_breaking_change: null next_review: 2026-08-23 change_sensitivity: low # === CONSTRAINTS === constraints: - "Comparison-based sorts cannot beat O(n log n) average case (proven lower bound)" - "Linear-time sorts (radix, counting, bucket) require assumptions about input distribution or key range" - "In-place sorts use O(1) extra memory but may sacrifice stability" - "Stability matters when sorting objects by multiple keys; unstable sorts destroy prior ordering" - "Worst-case O(n^2) quicksort occurs with sorted/reverse-sorted input and naive pivot selection" # === SKIP CONDITIONS === skip_this_unit_if: - condition: "Looking for search algorithms (binary search, hash lookup)" use_instead: "software/patterns/binary-search-variations/2026" - condition: "Need to sort a database result set (use ORDER BY, not application-level sorting)" use_instead: "Database query optimization with ORDER BY and indexes" - condition: "Need a data structure that maintains sorted order on insert" use_instead: "Balanced BST, skip list, or sorted set data structures" # === AGENT HINTS === inputs_needed: - key: data_characteristics question: "What does your input data look like?" type: choice options: ["nearly_sorted", "random", "many_duplicates", "reverse_sorted", "small_integers"] - key: size question: "How large is the dataset?" type: choice options: ["small (<1000)", "medium (1K-1M)", "large (>1M)"] - key: stability_needed question: "Do you need stable sorting (preserve order of equal elements)?" type: choice options: ["yes", "no", "unsure"] - key: memory_constraint question: "Is memory a constraint?" type: choice options: ["in_place_required", "O(n)_extra_ok", "no_constraint"] # === DISTRIBUTION === canonical_source: "https://knowledgelib.io/software/patterns/sorting-algorithms/2026" suggested_citation: "Source: knowledgelib.io -- AI Knowledge Library (verified 2026-02-24)" # === RELATED UNITS === related_kos: depends_on: [] related_to: - id: "software/patterns/binary-search-variations/2026" label: "Binary Search Variations" - id: "software/patterns/graph-algorithms/2026" label: "Graph Algorithms Reference" - id: "software/patterns/dynamic-programming/2026" label: "Dynamic Programming Patterns" solves: [] alternative_to: [] often_confused_with: - id: "software/patterns/search-algorithms/2026" label: "Search Algorithms (binary search, hash-based lookup)" # === SOURCES (7 authoritative sources) === # Types: official_docs, technical_blog, rfc_spec, academic_paper, community_resource, industry_report # Reliability: high, moderate_high, moderate, moderate_low, low, authoritative sources: - id: src1 title: "Sorting algorithm" author: Wikipedia Contributors url: https://en.wikipedia.org/wiki/Sorting_algorithm type: community_resource published: 2026-02-20 reliability: high - id: src2 title: "Time Complexities of all Sorting Algorithms" author: GeeksforGeeks url: https://www.geeksforgeeks.org/dsa/time-complexities-of-all-sorting-algorithms/ type: community_resource published: 2025-12-15 reliability: high - id: src3 title: "When to use each Sorting Algorithm" author: GeeksforGeeks url: https://www.geeksforgeeks.org/dsa/when-to-use-each-sorting-algorithms/ type: community_resource published: 2025-11-10 reliability: high - id: src4 title: "Timsort" author: Wikipedia Contributors url: https://en.wikipedia.org/wiki/Timsort type: community_resource published: 2026-01-15 reliability: high - id: src5 title: "Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo" author: VisuAlgo url: https://visualgo.net/en/sorting type: community_resource published: 2025-06-01 reliability: moderate_high - id: src6 title: "Counting Sort vs. Bucket Sort vs. Radix Sort" author: Baeldung url: https://www.baeldung.com/cs/radix-vs-counting-vs-bucket-sort type: technical_blog published: 2025-09-20 reliability: moderate_high - id: src7 title: "Comparison of Sorting Algorithms" author: EnjoyAlgorithms url: https://www.enjoyalgorithms.com/blog/comparison-of-sorting-algorithms/ type: technical_blog published: 2025-08-01 reliability: moderate_high --- # Sorting Algorithms Compared: Complete Reference ## TL;DR - **Bottom line**: Use your language's stdlib sort (TimSort/IntroSort) for 99% of cases; only reach for specialized algorithms when you have domain-specific constraints like integer-only keys or external storage. - **Key tool/command**: `sorted()` (Python), `Arrays.sort()` (Java), `Array.prototype.sort()` (JS), `sort.Slice()` (Go) - **Watch out for**: Worst-case O(n^2) with naive quicksort on sorted input; always use a randomized pivot or IntroSort variant. - **Works with**: All programming languages; algorithm properties are language-agnostic. ## Constraints - Comparison-based sorts provably cannot beat O(n log n) average-case time complexity (information-theoretic lower bound). [src1] - Linear-time sorts (radix, counting, bucket) only apply when input satisfies specific conditions: bounded integer range (counting), fixed-width keys (radix), or uniform distribution (bucket). [src6] - In-place sorting (O(1) extra space) and stability cannot always be achieved simultaneously -- choose one based on your requirements. [src1] - Unstable sorts (quicksort, heapsort, introsort) may reorder equal elements -- never use them when multi-key sort order must be preserved. [src2] - Naive quicksort degrades to O(n^2) on already-sorted or reverse-sorted input; production implementations must use randomized pivots, median-of-three, or switch to heapsort (IntroSort). [src1] ## Quick Reference | Algorithm | Best | Average | Worst | Space | Stable | Adaptive | When to Use | |---|---|---|---|---|---|---|---| | **QuickSort** | O(n log n) | O(n log n) | O(n^2) | O(log n) | No | No | General-purpose; fastest in practice for random data | | **MergeSort** | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No | When stability required; linked lists; external sorting | | **HeapSort** | O(n log n) | O(n log n) | O(n log n) | O(1) | No | No | Guaranteed O(n log n) with O(1) space; embedded systems | | **TimSort** | O(n) | O(n log n) | O(n log n) | O(n) | Yes | Yes | Python/Java stdlib; best for real-world partially-sorted data | | **IntroSort** | O(n log n) | O(n log n) | O(n log n) | O(log n) | No | No | C++ STL / .NET stdlib; quicksort with heapsort fallback | | **RadixSort** | O(nk) | O(nk) | O(nk) | O(n + k) | Yes | No | Fixed-width integers/strings; k = number of digits | | **CountingSort** | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes | No | Small integer range [0, k); subroutine for radix sort | | **BucketSort** | O(n + k) | O(n + k) | O(n^2) | O(n + k) | Yes* | No | Uniformly distributed floating-point values | | **InsertionSort** | O(n) | O(n^2) | O(n^2) | O(1) | Yes | Yes | Small arrays (n < 20-50); nearly sorted data; online sorting | | **ShellSort** | O(n log n) | O(n^(4/3)) | O(n^(3/2)) | O(1) | No | Yes | Embedded systems; better than insertion sort for medium n | Notes: *BucketSort stability depends on the inner sort used. TimSort's O(n) best case occurs when input has existing sorted runs. QuickSort's O(log n) space is for the recursion stack. [src1] [src2] [src7] ## Decision Tree ``` START |-- Is data already partially sorted or has natural runs? | |-- YES --> TimSort (stdlib sorted()/list.sort() in Python, Arrays.sort() for objects in Java) | +-- NO v |-- Are keys small integers with bounded range [0, k)? | |-- YES --> k < n? --> CountingSort | | k >= n but fixed-width? --> RadixSort | +-- NO v |-- Are values uniformly distributed floats in known range? | |-- YES --> BucketSort | +-- NO v |-- Is stability required (preserving order of equal elements)? | |-- YES --> MergeSort (or TimSort via stdlib) | +-- NO v |-- Is memory constrained (must be in-place)? | |-- YES --> Is worst-case guarantee needed? | | |-- YES --> HeapSort (O(n log n) guaranteed, O(1) space) | | +-- NO --> IntroSort (quicksort + heapsort fallback) | +-- NO v |-- Is dataset very small (n < 50)? | |-- YES --> InsertionSort | +-- NO v +-- DEFAULT --> Use stdlib sort (TimSort or IntroSort depending on language) ``` ## Step-by-Step Guide ### 1. Implement QuickSort with randomized pivot QuickSort is the most commonly studied sorting algorithm and the basis for many stdlib implementations. The critical detail is pivot selection -- always randomize to avoid O(n^2) worst case. [src1] ```python import random def quicksort(arr, low=0, high=None): if high is None: high = len(arr) - 1 if low < high: pivot_idx = partition(arr, low, high) quicksort(arr, low, pivot_idx - 1) quicksort(arr, pivot_idx + 1, high) def partition(arr, low, high): # Randomized pivot avoids O(n^2) on sorted input pivot_idx = random.randint(low, high) arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx] pivot = arr[high] i = low - 1 for j in range(low, high): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1 ``` **Verify**: `arr = [3,6,8,10,1,2,1]; quicksort(arr); print(arr)` --> expected output: `[1, 1, 2, 3, 6, 8, 10]` ### 2. Implement MergeSort for guaranteed O(n log n) with stability MergeSort divides the array into halves, sorts each recursively, and merges. It guarantees O(n log n) in all cases and is stable, but uses O(n) extra space. [src1] ```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]: # <= preserves stability result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result ``` **Verify**: `print(merge_sort([38, 27, 43, 3, 9, 82, 10]))` --> expected: `[3, 9, 10, 27, 38, 43, 82]` ### 3. Implement CountingSort for bounded integer ranges CountingSort achieves O(n + k) time by counting occurrences rather than comparing. It requires knowing the range of input values. [src6] ```python def counting_sort(arr, max_val=None): if not arr: return arr if max_val is None: max_val = max(arr) count = [0] * (max_val + 1) for num in arr: count[num] += 1 # Build output preserving stability output = [] for val in range(max_val + 1): output.extend([val] * count[val]) return output ``` **Verify**: `print(counting_sort([4, 2, 2, 8, 3, 3, 1]))` --> expected: `[1, 2, 2, 3, 3, 4, 8]` ### 4. Implement RadixSort for fixed-width integer keys RadixSort processes digits from least significant to most significant, using a stable sort (counting sort) as a subroutine. Achieves O(nk) where k is the number of digits. [src6] ```python def radix_sort(arr): if not arr: return arr max_val = max(arr) exp = 1 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 num in arr: idx = (num // exp) % 10 count[idx] += 1 for i in range(1, 10): count[i] += count[i - 1] # Traverse in reverse for stability for i in range(n - 1, -1, -1): idx = (arr[i] // exp) % 10 output[count[idx] - 1] = arr[i] count[idx] -= 1 return output ``` **Verify**: `print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))` --> expected: `[2, 24, 45, 66, 75, 90, 170, 802]` ## Code Examples ### Python: stdlib sorting with custom comparators ```python # Input: list of objects to sort # Output: sorted list (TimSort: stable, adaptive, O(n log n)) from functools import cmp_to_key # Basic sort (TimSort under the hood) nums = [5, 2, 8, 1, 9] sorted_nums = sorted(nums) # Returns new list nums.sort() # Sorts in-place # Sort by key function students = [("Alice", 85), ("Bob", 92), ("Charlie", 85)] by_grade = sorted(students, key=lambda s: s[1], reverse=True) # [('Bob', 92), ('Alice', 85), ('Charlie', 85)] # Stable: Alice stays before Charlie (both 85) # Multi-key sort: primary descending grade, secondary ascending name by_multi = sorted(students, key=lambda s: (-s[1], s[0])) # Custom comparator (rare, prefer key= when possible) def compare(a, b): return (a > b) - (a < b) sorted_custom = sorted(nums, key=cmp_to_key(compare)) ``` ### JavaScript: Array.prototype.sort with gotchas ```javascript // Input: array to sort // Output: sorted array (TimSort in V8/SpiderMonkey since ~2019) // GOTCHA: Default sort is lexicographic, not numeric! [10, 9, 8].sort(); // [10, 8, 9] -- WRONG for numbers [10, 9, 8].sort((a, b) => a - b); // [8, 9, 10] -- correct // Sort objects by property const items = [ { name: "Banana", price: 1.50 }, { name: "Apple", price: 0.99 }, { name: "Cherry", price: 2.00 } ]; items.sort((a, b) => a.price - b.price); // Stable sort (guaranteed since ES2019 / V8 7.0+) // For older engines, use a polyfill or mergesort library // String sort with locale awareness const words = ["resume", "Resume", "RESUME"]; words.sort((a, b) => a.localeCompare(b, "en", { sensitivity: "base" })); ``` ### Java: Arrays.sort and Collections.sort ```java // Input: array or List to sort // Output: sorted in-place // Arrays.sort(primitives) = Dual-Pivot QuickSort (unstable) // Arrays.sort(objects) = TimSort (stable) import java.util.Arrays; import java.util.Collections; import java.util.Comparator; int[] primitives = {5, 2, 8, 1}; Arrays.sort(primitives); // Dual-Pivot QuickSort, O(n log n) String[] names = {"Charlie", "Alice", "Bob"}; Arrays.sort(names); // TimSort (stable), natural ordering // Custom comparator Integer[] nums = {5, 2, 8, 1}; Arrays.sort(nums, Comparator.reverseOrder()); // Sort by multiple keys record Student(String name, int grade) {} Student[] students = { new Student("Alice", 85), new Student("Bob", 92) }; Arrays.sort(students, Comparator.comparingInt(Student::grade) .reversed() .thenComparing(Student::name)); ``` ### Go: sort.Slice and sort.SliceStable > Full script: [go-sort-slice-and-sort-slicestable.go](scripts/go-sort-slice-and-sort-slicestable.go) (28 lines) ```go // Input: slice to sort // Output: sorted in-place // sort.Slice = IntroSort variant (unstable) // sort.SliceStable = MergeSort variant (stable) package main # ... (see full script) ``` ## Anti-Patterns ### Wrong: Using bubble sort in production code ```python # BAD -- O(n^2) average and worst case; never use for real data def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr ``` ### Correct: Use stdlib sort ```python # GOOD -- TimSort: O(n log n), stable, adaptive, heavily optimized in C arr = [5, 3, 8, 1, 2] arr.sort() # In-place, fast, production-ready ``` ### Wrong: JavaScript numeric sort without comparator ```javascript // BAD -- default sort is lexicographic const prices = [100, 25, 3, 1000]; prices.sort(); // Result: [100, 1000, 25, 3] -- WRONG ``` ### Correct: Always provide numeric comparator ```javascript // GOOD -- explicit numeric comparison const prices = [100, 25, 3, 1000]; prices.sort((a, b) => a - b); // Result: [3, 25, 100, 1000] ``` ### Wrong: Naive quicksort pivot selection ```python # BAD -- always picking first/last element as pivot # Degrades to O(n^2) on sorted or reverse-sorted input def bad_partition(arr, low, high): pivot = arr[high] # Always last element # ... sorted input => every partition is maximally unbalanced ``` ### Correct: Randomized or median-of-three pivot ```python # GOOD -- randomized pivot prevents adversarial worst case import random def good_partition(arr, low, high): pivot_idx = random.randint(low, high) arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx] pivot = arr[high] # ... balanced partitions in expectation ``` ### Wrong: Ignoring stability when sorting by multiple keys ```python # BAD -- using unstable sort then wondering why secondary order is lost import heapq data = [("Alice", 85), ("Bob", 85), ("Charlie", 90)] # heapsort is not stable; Alice/Bob order not preserved within grade 85 ``` ### Correct: Use stable sort or sort by composite key ```python # GOOD -- Python's sorted() is stable (TimSort) data = [("Alice", 85), ("Bob", 85), ("Charlie", 90)] # Sort by grade descending, then name ascending (stable preserves name order) result = sorted(data, key=lambda x: (-x[1], x[0])) # [('Charlie', 90), ('Alice', 85), ('Bob', 85)] ``` ## Common Pitfalls - **Assuming O(n log n) is always optimal**: For small n (< 50), InsertionSort's low overhead often beats QuickSort/MergeSort due to cache locality and minimal bookkeeping. That's why TimSort and IntroSort use InsertionSort for small subarrays. Fix: let stdlib handle the threshold (typically 16-64 elements). [src4] - **Using quicksort on nearly-sorted data without safeguards**: Naive quicksort with first/last pivot degrades to O(n^2). Fix: use `random.choice()` for pivot or IntroSort which falls back to HeapSort after recursion depth exceeds 2*log(n). [src1] - **Choosing radix sort without checking key width**: RadixSort is O(nk) where k = number of digits. For 64-bit integers, k=20 (base 10) or k=8 (base 256). If n is small, nk > n log n. Fix: only use radix sort when n >> k, typically n > 10,000 with bounded keys. [src6] - **Forgetting that JavaScript sort mutates the array**: `Array.prototype.sort()` sorts in-place and returns the same reference. Fix: use `[...arr].sort()` or `arr.toSorted()` (ES2023+) if you need a new array. [src1] - **Ignoring external sorting for data that exceeds RAM**: When data does not fit in memory, MergeSort is the only standard algorithm that works efficiently with sequential access (disk/tape). Fix: use external merge sort (k-way merge with disk buffers). [src3] - **Assuming all stdlib sorts are the same**: Python uses TimSort (stable), Java uses Dual-Pivot QuickSort for primitives (unstable) but TimSort for objects (stable), C++ uses IntroSort (unstable), Go uses IntroSort variant (unstable). Fix: check your language's documentation for stability guarantees. [src4] ## Version History & Compatibility | Language/Runtime | Default Sort | Stable | Notes | |---|---|---|---| | Python 2.3+ (2002) | TimSort | Yes | Created by Tim Peters; adaptive merge sort + insertion sort | | Java 7+ (2011) | TimSort (objects) / Dual-Pivot QuickSort (primitives) | Objects only | `Arrays.sort(int[])` is unstable; `Arrays.sort(Object[])` is stable | | V8 / Chrome 70+ (2018) | TimSort | Yes | Replaced QuickSort; `Array.prototype.sort()` now guaranteed stable | | SpiderMonkey / Firefox 3+ | MergeSort | Yes | Has been stable since early versions | | C++ STL (GCC/Clang) | IntroSort | No | `std::sort` unstable; `std::stable_sort` uses MergeSort | | .NET / C# | IntroSort | No | `Array.Sort` unstable; `OrderBy` (LINQ) is stable | | Go 1.19+ (2022) | pdqsort | No | `sort.Slice` unstable; `sort.SliceStable` uses merge sort | | Swift 5+ (2019) | TimSort | Yes | Replaced IntroSort with TimSort | | Rust | TimSort variant | Yes | `sort()` stable; `sort_unstable()` uses pdqsort | ## When to Use / When Not to Use | Use When | Don't Use When | Use Instead | |---|---|---| | General-purpose sorting of any comparable data | Keys are small bounded integers | CountingSort or RadixSort | | Need stable sort with good average performance | Memory is extremely constrained (embedded) | HeapSort (O(1) space, unstable) | | Data has natural runs or is partially sorted | Data is truly random and you need minimal overhead | IntroSort (avoids TimSort's merge overhead) | | Sorting linked lists or external data on disk | Random access is available and cheap | QuickSort-based in-place sort | | Fixed-width integer keys with n > 10,000 | Keys are complex objects or variable-length strings | Comparison-based sort with custom comparator | | Need worst-case O(n log n) guarantee (real-time) | Average case is sufficient | HeapSort or MergeSort | ## Important Caveats - Algorithm benchmarks vary dramatically by hardware, cache size, and data distribution. Theoretical complexity does not capture constant factors -- always benchmark on your actual data if performance is critical. [src7] - TimSort exploits existing runs in data (common in real-world datasets) and achieves O(n) on fully sorted input. Random benchmark data understates TimSort's practical advantage. [src4] - Parallel sorting (parallel merge sort, parallel quicksort) can provide significant speedups on multi-core hardware but introduces complexity and overhead for small datasets. - The choice between stable and unstable sort has correctness implications, not just performance. If you sort records by multiple fields sequentially, an unstable sort on the second field may destroy the ordering from the first sort. - For string sorting, locale-aware comparison (`localeCompare` in JS, `Collator` in Java) can be significantly slower than byte-wise comparison. Profile before optimizing. ## Related Units - [Binary Search Variations](/software/patterns/binary-search-variations/2026) - [Graph Algorithms Reference](/software/patterns/graph-algorithms/2026) - [Dynamic Programming Patterns](/software/patterns/dynamic-programming/2026)