Click image to open full size
Algorithms Sorting and Searching Reference Cheat Sheet
A printable reference covering sorting algorithms, searching algorithms, asymptotic bounds, stability, in-place behavior, and selection strategies for college.
Related Tools
Related Labs
Related Worksheets
Related Infographics
This cheat sheet summarizes the main sorting and searching algorithms used in college computer science courses. It helps students compare algorithms by time complexity, space complexity, stability, and practical use cases. These comparisons are essential for analyzing code performance and choosing the right algorithm for a data structure or input pattern. A compact reference is especially useful when studying algorithm design, data structures, and technical interview problems. The core ideas include asymptotic analysis, comparison sorting lower bounds, divide-and-conquer sorting, hashing, binary search, and selection. Sorting algorithms are usually judged by best, average, and worst-case running time, plus whether they preserve equal-key order. Searching algorithms depend heavily on data organization, since linear search works on any list but binary search requires sorted data. Hash tables often give expected O(1) search, but their worst case depends on collisions and implementation details.
Key Facts
- Linear search checks items one at a time and runs in O(n) time with O(1) extra space.
- Binary search on a sorted array runs in O(log n) time because each comparison halves the remaining search interval.
- Any comparison-based sorting algorithm has a worst-case lower bound of Omega(n log n) comparisons.
- Merge sort runs in O(n log n) time in the best, average, and worst cases, and standard array merge sort uses O(n) extra space.
- Quicksort has average time O(n log n), worst-case time O(n^2), and expected O(log n) recursion depth when pivots are well balanced.
- Heapsort runs in O(n log n) worst-case time, uses O(1) extra array space, and is usually not stable.
- Insertion sort runs in O(n) time on nearly sorted input but O(n^2) time in the average and worst cases.
- Counting sort runs in O(n + k) time when keys are integers in a range of size k, and it is not comparison-based.
Vocabulary
- Asymptotic complexity
- A way to describe how an algorithm's running time or memory use grows as the input size n becomes large.
- Stable sort
- A sorting algorithm that keeps equal-key elements in the same relative order they had in the input.
- In-place algorithm
- An algorithm that uses only a small constant or logarithmic amount of extra memory beyond the input storage.
- Comparison sort
- A sorting algorithm that determines order only by comparing pairs of elements.
- Hash table
- A data structure that maps keys to array positions using a hash function to support fast expected search, insert, and delete.
- Pivot
- The element chosen in quicksort or selection algorithms to partition the input into smaller and larger groups.
Common Mistakes to Avoid
- Using binary search on an unsorted array is wrong because the halving decision only works when the data is ordered.
- Calling quicksort always O(n log n) is wrong because poor pivot choices can produce O(n^2) worst-case time.
- Assuming every O(n log n) sort is stable is wrong because heapsort and many in-place quicksort implementations do not preserve equal-key order.
- Ignoring extra space is wrong because merge sort's O(n) auxiliary array may matter even when its time complexity is optimal for comparison sorting.
- Comparing counting sort directly with comparison sorts without checking k is wrong because its O(n + k) time is efficient only when the key range is reasonable.
Practice Questions
- 1 A sorted array contains 1,024 elements. What is the maximum number of comparisons binary search needs to find an item or determine it is absent?
- 2 An insertion sort processes an array of 5,000 elements that is already sorted. What is its asymptotic running time, and why?
- 3 Counting sort is used on n = 20,000 records with integer keys from 0 to 999. What is the asymptotic running time in terms of n and k, and what is k here?
- 4 A database table is frequently searched by exact student ID and rarely printed in sorted order. Explain whether a hash table or a balanced binary search tree is the better primary structure.