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.
Understanding Algorithms Sorting and Searching Reference
A useful way to understand sorting is to picture the work done on the data. Comparison sorts learn order only by asking whether one item comes before another. Each answer removes some possible orders, but many possibilities remain when the list is large.
That is why no comparison method can guarantee fewer than about n log n comparisons in the general case. Counting sort avoids this limit because it uses the actual integer values as positions in a count array.
This works well for exam scores from zero to one hundred or dates within a small range. It becomes wasteful when possible values cover a huge range, such as unique identification numbers.
Stability matters when records have more than one field. Imagine a class list first sorted by student name, then sorted by grade. A stable second sort keeps students with the same grade in name order.
An unstable sort may scramble that earlier order. In place has a different meaning. An in place algorithm rearranges the existing array while using very little extra memory.
This can matter on devices with limited memory or when processing a very large file. There is often a tradeoff.
Merging is simple and reliably fast, yet merging array sections usually needs a separate temporary area. Heap based sorting saves memory, though its movement pattern can make it less friendly to the processor cache.
The input pattern can change the best choice more than a table of bounds suggests. Insertion sort is slow on a random large list, but it does very little work when items are already nearly in order. For this reason, practical library sorts often use a simple method on tiny pieces, then use a faster divide and conquer method for larger pieces.
Quicksort depends strongly on pivot choice. A pivot near the middle value splits work into two similar parts.
A poor pivot can repeatedly leave one large part, causing much more work. Random pivots or carefully chosen sample pivots reduce the chance of this problem, but they do not remove the theoretical bad case.
Searching has its own hidden costs. Binary search is excellent for repeated lookups in a sorted array, but keeping the array sorted can be expensive when new items arrive often. Inserting one item may require shifting many later items.
Hash tables are often a better fit for a dictionary, such as matching usernames to account records. Their expected speed relies on a hash function spreading keys across buckets and on resizing the table before it becomes too full. Collisions are normal, not necessarily an error.
The implementation must resolve them by storing a small group at a bucket or by finding another open position. When studying these algorithms, trace a small example by hand.
Track comparisons, swaps, recursion calls, and extra storage. This reveals details that big O notation intentionally hides.