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?
Understanding Sorting Algorithms Comparison
The most useful comparison comes from imagining the list getting much larger. A method whose work grows with the square of the number of items may seem fine for twenty values, yet it becomes slow for thousands. When the list doubles in size, its work can become roughly four times greater.
Methods whose work grows as the number of items times its logarithm scale more gently. The logarithm appears when an algorithm repeatedly reduces a task into smaller parts. Merge sort does this by splitting lists.
Heapsort uses levels in a tree shaped structure. These growth patterns usually matter more than one timing test on a particular computer.
The starting order of the data can change the result a lot. Insertion sort is practical when most items are already close to their final positions. It only needs to move an item a short distance in that case.
This is why some real software uses insertion sort for tiny pieces of a larger sorting job. Quicksort can be very fast when its pivot divides the data into fairly even groups. A poor pivot can leave one huge group and one tiny group repeatedly.
That creates its bad case. Good quicksort implementations choose pivots carefully or switch to a safer method when partitions become unbalanced.
Stability matters when each item contains more information than the value being sorted. Imagine student records sorted first by first name, then by grade level. If the second sort is stable, students with the same grade level keep their earlier first name order.
This makes multi step sorting predictable. An unstable method may rearrange equal records, which can make results look random even when every grade value is correct.
Stability is not automatically better. It is only needed when the existing order of equal items carries meaning.
Memory is another tradeoff that affects real programs. An in place method rearranges items within the original array, so it is useful when memory is limited. Merge sort usually creates temporary storage while combining sorted sections.
That extra storage helps make merging simple and predictable, but it can be expensive for very large datasets. When learning or coding a sort, test more than ordinary random lists. Use an empty list, one item, repeated values, an already ordered list, reverse order, and negative values.
Check that every original item remains present. Check the order is correct.
For stable algorithms, label equal values so their original order can be checked. These tests reveal mistakes in comparisons, loop limits, pivot handling, and merging.