Click image to open full size
Computer Science
Grade 9-12
Sorting Algorithms Comparison Cheat Sheet
A printable reference covering bubble sort, selection sort, insertion sort, merge sort, quicksort, heapsort, time complexity, space complexity, and stability for grades 9-12.
Related Tools
Related Labs
Related Worksheets
Sorting algorithms arrange data into a useful order, such as smallest to largest or alphabetically. This cheat sheet compares common sorting methods so students can choose the right algorithm for a situation. It is especially useful for understanding speed, memory use, and tradeoffs in computer science courses. The focus is on readable comparisons rather than code details.
Key Facts
- Bubble sort repeatedly swaps adjacent out-of-order items and has average and worst-case time complexity O(n^2).
- Selection sort repeatedly selects the smallest remaining item and has best, average, and worst-case time complexity O(n^2).
- Insertion sort builds a sorted section one item at a time and runs in O(n) time when the input is already nearly sorted.
- Merge sort splits the list, sorts each half, and merges them, giving O(n log n) time in best, average, and worst cases.
- Quicksort partitions around a pivot and has average time complexity O(n log n), but worst-case time complexity O(n^2).
- Heapsort uses a heap data structure and runs in O(n log n) time in best, average, and worst cases.
- A stable sort preserves the relative order of equal values, while an unstable sort may change that order.
- In-place sorting uses O(1) or very small extra memory, while merge sort usually needs O(n) extra space.
Vocabulary
- Sorting algorithm
- A procedure that rearranges data into a chosen order, such as ascending or descending order.
- Time complexity
- A measure of how the running time of an algorithm grows as the input size n increases.
- Space complexity
- A measure of how much extra memory an algorithm needs as the input size n increases.
- Stable sort
- A sorting algorithm that keeps equal items in the same relative order they had before sorting.
- In-place sort
- A sorting algorithm that rearranges items using only a small amount of extra memory.
- Pivot
- The chosen value used by quicksort to divide a list into smaller and larger parts.
Common Mistakes to Avoid
- Assuming every O(n log n) sort is always faster is wrong because small inputs, nearly sorted data, and constant factors can make simpler algorithms faster.
- Forgetting quicksort's worst case is wrong because a poor pivot choice can make quicksort run in O(n^2) time.
- Calling selection sort stable by default is wrong because standard selection sort can move equal items out of their original relative order.
- Ignoring memory use is wrong because merge sort is fast but usually needs O(n) extra space, which may matter for large data sets.
- Confusing best case and average case is wrong because insertion sort can be O(n) on nearly sorted data but O(n^2) on random or reversed data.
Practice Questions
- 1 A list has 1,000 items. About how many growth steps does an O(n^2) algorithm represent compared with n, and why can this become slow?
- 2 If merge sort processes 64 items, how many times can the list be split in half before reaching lists of size 1?
- 3 Choose a good sorting algorithm for a nearly sorted list of 20 numbers and explain your choice using time complexity.
- 4 A database has student records sorted by last name, and you now sort by grade level. Why might a stable sort be important?