Sorting algorithms are fundamental to computer science education and software engineering. Whether you are preparing for a midterm in a data structures course (such as CS 61B) or optimizing a data pipeline, understanding the exact trade-offs between sorting methods is essential.
While asymptotic Big-O notation describes how algorithms scale as inputs grow toward infinity, actual runtime on real-world inputs depends on constant factors, memory access patterns, comparison counts, and element moves.
This guide evaluates the six classic comparison-based sorting algorithms: Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quick Sort (both Lomuto and Hoare partition schemes), and Heap Sort. We run each algorithm through the exact same five-element benchmark array:
[5, 3, 8, 3, 1]
Every comparison, swap, and array write below is computed directly using ToolSphere's tested sorting engine. You can also trace custom inputs step by step using our interactive Sorting Algorithm Visualizer.
Big-O Complexity and Algorithmic Properties
The table below summarizes the theoretical time complexity, auxiliary space requirements, in-place behavior, and stability for each algorithm.
| Algorithm | Best Time | Average Time | Worst Time | Auxiliary Space | In-Place? | Stable? |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | Yes | No |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | No | Yes |
| Quick Sort (Lomuto) | O(n log n) | O(n log n) | O(n²) | O(log n) avg, O(n) worst | Yes | No |
| Quick Sort (Hoare) | O(n log n) | O(n log n) | O(n²) | O(log n) avg, O(n) worst | Yes | No |
| Heap Sort | O(n log n)* | O(n log n) | O(n log n) | O(1) | Yes | No |
*Heap Sort best-case time is O(n) when all keys are identical, and O(n log n) when keys are distinct.
Key Takeaways from Big-O Bounds
- Comparison Lower Bound: Any comparison-based sorting algorithm requires at least Ω(n log n) comparisons in the worst case to distinguish among the n! possible permutations of n distinct items.
- Space vs. Stability Trade-off: Merge Sort achieves a guaranteed O(n log n) worst-case time and preserves stability, but requires O(n) auxiliary memory for buffer merging. Heap Sort achieves guaranteed O(n log n) time in O(1) auxiliary space, but sacrifices stability.
- Adaptive Algorithms: Insertion Sort and Bubble Sort adapt to pre-sorted inputs. When an array is already sorted, both detect this condition in a single linear O(n) pass. In contrast, Selection Sort always scans the remaining unsorted suffix, executing Θ(n²) comparisons regardless of initial order.
Benchmark Comparison on the Same Input
To observe concrete operational differences, we run all algorithms on the same input list of 5 integers:
Initial Array: [5, 3, 8, 3, 1]
Tagged Elements: [5₀, 3₁, 8₂, 3₃, 1₄]
The array contains two duplicate values: 3₁ at index 1 and 3₃ at index 3. Tracking their original subscripts reveals whether each algorithm preserves stability by keeping 3₁ before 3₃ in the final output.
Here are the exact counts produced by tracing the algorithms:
| Algorithm | Comparisons | Swaps | Array Writes | Final Tagged Indices | Stable on Benchmark? |
|---|---|---|---|---|---|
| Bubble Sort | 10 | 7 | 14 | [4, 1, 3, 0, 2] | Yes |
| Insertion Sort | 9 | 0 | 11 | [4, 1, 3, 0, 2] | Yes |
| Selection Sort | 10 | 3 | 6 | [4, 1, 3, 0, 2] | Accidental* |
| Merge Sort | 7 | 0 | 12 | [4, 1, 3, 0, 2] | Yes |
| Quick Sort (Lomuto) | 8 | 3 | 6 | [4, 1, 3, 0, 2] | Accidental* |
| Quick Sort (Hoare) | 20 | 4 | 8 | [4, 3, 1, 0, 2] | No (Inverted) |
| Heap Sort | 9 | 7 | 14 | [4, 1, 3, 0, 2] | Accidental* |
*Selection Sort, Lomuto Quick Sort, and Heap Sort are inherently unstable algorithms. Although duplicate values happened to retain their relative order on this particular 5-element sequence, they fail stability on other simple permutations (such as [2, 2, 1]). In contrast, Hoare Quick Sort actively reverses the duplicate 3s on this exact input.
Detailed Step-by-Step Traces
1. Bubble Sort
Bubble Sort iterates through the array from left to right, comparing adjacent items and swapping them when out of order. Each full pass bubbles the largest unsorted key to the end of the unsorted segment. With an early-exit optimization, sorting terminates if a full pass completes without any swaps.
- Total Comparisons: 10
- Total Swaps: 7 (each swap performs 2 array writes = 14 writes)
- Pass 1:
- Compare 5 with 3 → swap positions 1 and 2:
[3, 5, 8, 3, 1] - Compare 5 with 8 → no swap
- Compare 8 with 3 → swap positions 3 and 4:
[3, 5, 3, 8, 1] - Compare 8 with 1 → swap positions 4 and 5:
[3, 5, 3, 1, 8] - End of pass 1: element 8 is fixed at position 5.
- Compare 5 with 3 → swap positions 1 and 2:
- Pass 2:
- Compare 3 with 5 → no swap
- Compare 5 with 3 → swap positions 2 and 3:
[3, 3, 5, 1, 8] - Compare 5 with 1 → swap positions 3 and 4:
[3, 3, 1, 5, 8] - End of pass 2: element 5 is fixed at position 4.
- Pass 3:
- Compare 3 with 3 → equal keys, no swap (maintains stability)
- Compare 3 with 1 → swap positions 2 and 3:
[3, 1, 3, 5, 8] - End of pass 3: element 3 is fixed at position 3.
- Pass 4:
- Compare 3 with 1 → swap positions 1 and 2:
[1, 3, 3, 5, 8] - End of pass 4: prefix is sorted.
- Compare 3 with 1 → swap positions 1 and 2:
- Sorted Array:
[1, 3, 3, 5, 8]with original indices[4, 1, 3, 0, 2].
2. Insertion Sort
Insertion Sort builds a sorted prefix one element at a time. For each new key, it shifts larger preceding keys one position to the right and inserts the saved key into the vacated slot. Because elements shift rather than trade places via two-element exchanges, Insertion Sort records 0 swaps and 11 single array writes.
- Total Comparisons: 9
- Total Swaps: 0
- Total Array Writes: 11
- Insert Key 3 (position 2): Compares 5 > 3. Shifts 5 right to position 2; writes 3 to position 1. Prefix
[3, 5]sorted. (1 comparison, 2 writes). - Insert Key 8 (position 3): Compares 5 < 8. Key 8 stays in position 3. Prefix
[3, 5, 8]sorted. (1 comparison, 1 write). - Insert Key 3₃ (position 4): Compares 8 > 3 (shift 8), 5 > 3 (shift 5), 3 == 3. Because
3 > 3is false, shifting halts immediately after the first3₁. Key3₃is written into position 2. Prefix[3, 3, 5, 8]sorted. (3 comparisons, 3 writes). - Insert Key 1 (position 5): Compares 8 > 1 (shift 8), 5 > 1 (shift 5), 3 > 1 (shift second 3), 3 > 1 (shift first 3). Inserts 1 into position 1. (4 comparisons, 5 writes).
- Sorted Array:
[1, 3, 3, 5, 8]with original indices[4, 1, 3, 0, 2].
3. Selection Sort
Selection Sort divides the list into a sorted prefix and an unsorted suffix. In each round, it scans the entire unsorted suffix to identify the minimum key and swaps it into the current prefix boundary.
- Total Comparisons: 10 (always 4 + 3 + 2 + 1 = 10 comparisons)
- Total Swaps: 3 (self-swaps are skipped)
- Total Array Writes: 6
- Round 1: Scans positions 2 through 5. Minimum key is 1 at position 5. Swaps position 1 (5) and position 5 (1). Array:
[1, 3, 8, 3, 5]. (4 comparisons, 1 swap). - Round 2: Scans positions 3 through 5. Minimum key is 3 at position 2. Self-swap is skipped. Array:
[1, 3, 8, 3, 5]. (3 comparisons, 0 swaps). - Round 3: Scans positions 4 through 5. Minimum key is 3 at position 4. Swaps position 3 (8) and position 4 (3). Array:
[1, 3, 3, 8, 5]. (2 comparisons, 1 swap). - Round 4: Compares position 4 (8) with position 5 (5). Minimum is 5 at position 5. Swaps position 4 (8) and position 5 (5). Array:
[1, 3, 3, 5, 8]. (1 comparison, 1 swap). - Sorted Array:
[1, 3, 3, 5, 8]with original indices[4, 1, 3, 0, 2].
4. Merge Sort
Merge Sort is a divide-and-conquer algorithm. It recursively bisects the list into halves until reaching single-element base cases, then merges sorted sublists back together using a temporary buffer.
- Total Comparisons: 7
- Total Swaps: 0 (writes back from temporary merge buffers)
- Total Array Writes: 12
- Merge 1 (positions 1–2): Merges
[5]and[3]→ compares 5 with 3, writes[3, 5]. (1 comparison, 2 writes). - Merge 2 (positions 1–3): Merges
[3, 5]and[8]→ writes[3, 5, 8]. (2 comparisons, 3 writes). - Merge 3 (positions 4–5): Merges
[3]and[1]→ compares 3 with 1, writes[1, 3]. (1 comparison, 2 writes). - Merge 4 (positions 1–5): Merges left
[3₁, 5, 8]with right[1, 3₃]:- Compare 3₁ with 1 → take 1 from right.
- Compare 3₁ with 3₃ → tie! Merge Sort takes the left element on ties (
left[i] <= right[j]), ensuring stability. Takes 3₁. - Compare 5 with 3₃ → take 3₃ from right.
- Flush remaining left keys 5 and 8.
- Sorted Array:
[1, 3, 3, 5, 8]with original indices[4, 1, 3, 0, 2].
5. Quick Sort: Lomuto vs. Hoare Partitioning
Quick Sort selects a pivot element and partitions the array so keys less than the pivot sit to its left and keys greater sit to its right. The partitioning scheme substantially affects performance and comparison counts.
Lomuto Partition (Single Direction)
Lomuto uses the last element of the range as the pivot and maintains an index scanning left-to-right.
- Total Comparisons: 8
- Total Swaps: 3
- Total Array Writes: 6
- Partition 1 (range 1–5, pivot = 1): Compares keys 5, 3, 8, 3 against pivot 1. None are <= 1. Swaps position 1 (5) with position 5 (pivot 1). Pivot 1 is fixed at position 1. Array:
[1, 3, 8, 3, 5]. (4 comparisons, 1 swap). - Partition 2 (range 2–5, pivot = 5): Keys 3, 8, 3 are compared with 5. Swaps position 3 (8) with position 4 (3), then swaps position 4 (8) with pivot 5. Pivot 5 is fixed at position 4. Array:
[1, 3, 3, 5, 8]. (3 comparisons, 2 swaps). - Partition 3 (range 2–3, pivot = 3): Compares key 3 <= 3. Self-swap skipped. Pivot fixed at position 3. Array:
[1, 3, 3, 5, 8]. (1 comparison, 0 swaps).
Hoare Partition (Two Pointers)
Hoare uses the middle element as pivot and advances two pointers inward from both ends. When the left pointer encounters a value >= pivot and the right pointer encounters a value <= pivot, they swap values.
- Total Comparisons: 20 (counts all boundary stop checks)
- Total Swaps: 4
- Total Array Writes: 8
- Duplicate Inversion: During partitioning of subarray
[5, 3₁, 1, 3₃], the inward pointers halt at position 1 (value 5) and position 4 (value3₃). Swapping them moves3₃to the front of the array before3₁. - Final Tagged Order:
[1₄, 3₃, 3₁, 5₀, 8₂]with original indices[4, 3, 1, 0, 2]. This demonstrates first-hand why Hoare Quick Sort is unstable.
6. Heap Sort
Heap Sort organizes elements into a binary heap data structure inside the array. It first converts the array into a max-heap in bottom-up fashion (using sift-down operations), then repeatedly extracts the maximum root element to the end of the array.
- Total Comparisons: 9
- Total Swaps: 7
- Total Array Writes: 14
- Phase 1: Build Max-Heap:
- Sifts down internal parent nodes starting from index
floor(n/2) - 1. - Node at position 2 (value 3) has children 3 and 1; no sift required (2 comparisons).
- Node at position 1 (value 5) has children 3 and 8; swaps position 1 (5) and position 3 (8) (2 comparisons, 1 swap). Max-heap established:
[8, 3, 5, 3, 1].
- Sifts down internal parent nodes starting from index
- Phase 2: Extract Maximums:
- Swap root 8 with end key 1; sift down root key 1 → Array:
[5, 3, 1, 3, 8]. (2 comparisons, 2 swaps). - Swap root 5 with end key 3; sift down root key 3 → Array:
[3, 3, 1, 5, 8]. (2 comparisons, 1 swap). - Swap root 3 with end key 1; sift down root key 1 → Array:
[3, 1, 3, 5, 8]. (1 comparison, 2 swaps). - Swap root 3 with position 2 → Array:
[1, 3, 3, 5, 8]. (0 comparisons, 1 swap).
- Swap root 8 with end key 1; sift down root key 1 → Array:
- Sorted Array:
[1, 3, 3, 5, 8]with original indices[4, 1, 3, 0, 2].
Stability Explained with Counterexamples
A sorting algorithm is stable if two objects with equal keys appear in the same relative order in the sorted output as they did in the input.
Stability is essential when sorting objects on multiple fields. For example, if you sort a roster of students alphabetically by name and subsequently sort them by GPA, a stable sort preserves alphabetical ordering within each GPA bracket.
Why Selection Sort is Unstable
Selection Sort swaps the minimum item of the remaining suffix with the item currently occupying the front of that suffix. This long-range swap can leap over equal keys:
Consider [2_a, 2_b, 1]:
- The minimum key in the list is
1at index 2. - Selection Sort swaps index 0 (
2_a) with index 2 (1). - The array becomes
[1, 2_b, 2_a]. - The duplicate
2_bnow precedes2_a. The relative order of equal keys was reversed.
Why Quick Sort and Heap Sort are Unstable
- Quick Sort: Both Lomuto and Hoare partition schemes perform long-distance swaps across the pivot boundary. As observed in our Hoare trace on
[5, 3₁, 8, 3₃, 1],3₃swapped into position 1, jumping ahead of3₁. - Heap Sort: During heap construction and root extraction, items move along tree paths determined by parent-child indices
(2i + 1)and(2i + 2). Equal items located in different subtrees have their relative array positions shuffled during sift-down operations.
Practical Decision Matrix: Which Algorithm Should You Use?
In software development, pure textbook algorithms are often combined into hybrid routines:
- Use Insertion Sort when: The array is small (typically n < 32–64 elements) or already nearly sorted. Its low constant factors, zero dynamic memory overhead, and cache-friendly sequential access make it unbeatable on small inputs.
- Use Merge Sort when: Stability is strictly required and predictable O(n log n) performance is needed regardless of input distribution. It is also the basis for external sorting algorithms operating on disks.
- Use Quick Sort (or Introsort) when: Sorting in-place in general-purpose memory. Standard library routines like C++
std::sortuse Introsort (Quick Sort switching to Heap Sort if recursion depth exceeds 2 log n, and Insertion Sort on small partitions). - Use Timsort (Hybrid Merge + Insertion): The default sorting algorithm in Python (
list.sort) and Java (Arrays.sortfor objects). Timsort identifies existing runs of ordered data and merges them using an adaptive merge routine.
Frequently Asked Questions
Why is Quick Sort generally faster in practice than Merge Sort and Heap Sort?
Quick Sort features excellent spatial locality of reference. Its inner partitioning loop sequentially scans contiguous array elements in memory, maximizing hardware CPU L1/L2 cache hits. In contrast, Heap Sort makes wide index jumps through the binary tree (leaping between parent i and children 2i), causing frequent CPU cache misses. Merge Sort requires allocating and copying data into auxiliary buffers.
Can Selection Sort ever be implemented as a stable sort?
Standard Selection Sort is inherently unstable because it uses array swaps. You can make it stable by shifting elements rather than swapping (inserting the minimum element into its position and shifting intermediary elements right), but doing so requires O(n) element shifts per round, increasing write operations from O(n) to O(n²).
What causes Quick Sort to degrade to its O(n²) worst-case time?
Quick Sort degrades to quadratic O(n²) time when partitions are consistently unbalanced (e.g., one partition contains n − 1 elements and the other contains 0). With a naive last-element pivot rule, an already sorted or reverse-sorted array triggers this worst case. Modern implementations mitigate this using median-of-three pivot selection or randomized pivots.
Why does Merge Sort require O(n) auxiliary space for arrays?
During the merge step, elements from two sorted subarrays must be interleaved into a new sorted sequence. Because overwriting the array in place without a buffer would destroy unprocessed elements, an auxiliary buffer of size n is required. While in-place merge algorithms exist, their high constant factors make them impractical in production.
Why is Bubble Sort rarely used in production software?
Bubble Sort performs adjacent swaps, leading to high comparison and write overhead. On average, it requires n(n − 1)/2 comparisons and roughly half as many swaps. Even Insertion Sort, which shares the same O(n²) worst-case bound, performs substantially fewer comparisons and writes on typical datasets.
How does Insertion Sort detect an already sorted array in O(n) time?
When the array is already sorted in non-decreasing order, each newly considered element a[i] is immediately compared with a[i - 1]. Because a[i - 1] <= a[i], the inner while loop condition terminates after exactly one comparison without executing any shifts. For an array of size n, this results in exactly n − 1 comparisons and 0 swaps.
What is the difference between Lomuto and Hoare partitioning in Quick Sort?
Lomuto uses a single index scanning in one direction and chooses the last element as pivot, executing roughly 3 times as many swaps on average. Hoare uses two pointers moving toward each other from opposite ends; it performs significantly fewer swaps and handles duplicate elements more efficiently, but its implementation is more prone to off-by-one errors.
Why is Heap Sort useful if Quick Sort is faster on average?
Heap Sort guarantees strict O(n log n) worst-case time complexity while requiring only O(1) auxiliary space. In real-time systems, mission-critical avionics, and safety-critical kernels where O(n²) worst-case latency or unbounded call-stack growth cannot be tolerated, Heap Sort provides deterministic bounds without allocating heap memory.
How does Timsort improve upon standard Merge Sort?
Timsort inspects the input for pre-existing non-decreasing or strictly decreasing sequences (called "natural runs"). It reverses descending runs and extends short runs using binary insertion sort up to a minimum chunk size (minrun). It then balances run sizes on a stack and merges them using galloping search mode, achieving O(n) time on partially sorted real-world data.
What is Introsort and why do standard libraries use it?
Introsort (introspective sort) begins with Quick Sort to take advantage of high CPU cache efficiency. It monitors the recursion tree depth; if the depth exceeds a threshold (typically 2 · ⌊log₂ n⌋), it switches to Heap Sort to guarantee an O(n log n) worst-case time bound. When partitions become smaller than 16 elements, it switches to Insertion Sort.
Interactive Practice
Explore how each pass rearranges elements in real time. Launch our Sorting Algorithm Visualizer to load custom numbers, step forward and backward through comparisons, inspect memory write counts, and trace duplicate key stability.
Use the Data Structure Visualizer to trace tree and heap operations. For a related walkthrough, read Master Theorem: 10 Solved Examples.