Click image to open full size
Sorting Algorithms Visual Cheat Sheet
Bubble, Merge, Quick Sort and Beyond
Related Tools
Related Labs
Sorting is one of the most fundamental operations in computer science — transforming a list into a predictable order enables efficient searching and many other algorithms. Different sorting algorithms make different trade-offs between time complexity, space complexity, stability (whether equal elements maintain their original relative order), and implementation simplicity. Simple algorithms like Bubble Sort and Insertion Sort are O(n²) but have near-zero overhead for small or nearly-sorted arrays. Divide-and-conquer algorithms like Merge Sort and Quick Sort achieve O(n log n) average performance but require more complex implementation.
Merge Sort guarantees O(n log n) in all cases and is stable, making it the preferred choice when stability matters (e.g., sorting a list of records by one field while preserving a previous sort by another field). Quick Sort is typically faster in practice due to cache efficiency but has O(n²) worst case with bad pivot selection. Insertion Sort is O(n) on nearly-sorted data, so many hybrid algorithms (like Timsort, used in Python and Java) switch to Insertion Sort for small subarrays.
Key Facts
- Bubble Sort: O(n²) time; swaps adjacent elements; simple but inefficient
- Insertion Sort: O(n²) average, O(n) best (nearly sorted); stable; good for small n
- Selection Sort: O(n²) always; not stable; minimizes swaps
- Merge Sort: O(n log n) always; stable; requires O(n) extra space
- Quick Sort: O(n log n) average, O(n²) worst; in-place; not stable by default
- Stable sort: equal elements keep their original relative order — important when sorting by multiple keys
Vocabulary
- Stable sort
- A sorting algorithm that preserves the relative order of elements with equal keys.
- In-place sort
- A sorting algorithm that requires only O(1) additional memory beyond the input array (no large auxiliary arrays).
- Divide and conquer
- An algorithm design paradigm that splits the problem into smaller subproblems, solves them recursively, and combines results.
- Pivot
- In Quick Sort, the element chosen as the reference point around which the array is partitioned into smaller and larger elements.
- Timsort
- A hybrid stable sort combining Merge Sort and Insertion Sort; used as the default in Python and Java's Arrays.sort() for objects.
Common Mistakes to Avoid
- Thinking Bubble Sort is good because it's simple. Bubble Sort's O(n²) performance makes it impractical for any real dataset with more than a few hundred elements. Use Insertion Sort for simple sorts instead.
- Assuming Quick Sort is always O(n log n). Quick Sort degrades to O(n²) when the pivot is consistently the smallest or largest element. Randomized pivot selection or median-of-three prevents this in practice.
- Ignoring stability when choosing a sort. If you need to sort a table of employees by salary and then by department, stability ensures the salary order is preserved within each department.
- Forgetting Merge Sort's space requirement. Merge Sort needs O(n) auxiliary space. For in-place sorting with O(n log n) time, use Heap Sort (though it is not stable and has worse cache performance).
Practice Questions
- 1 Trace Bubble Sort on the array [5, 3, 8, 1, 2]. Show the array after each pass through.
- 2 Why is Merge Sort preferred over Quick Sort when sorting a linked list?
- 3 An application sorts customer records first by state (alphabetical), then by last name within each state. Which sorting property (stable or unstable) is required, and why?