Difficulty: Beginner | Prerequisites: Data Structures study notes (arrays, linked lists). Familiarity with Big-O notation is helpful.
Once you have data in a structure, you need to do things with it, and the two most fundamental operations are sorting (putting elements in order) and searching (finding a specific element). Nearly every application you will build touches one or both. This set of notes covers the core sorting algorithms (bubble sort, insertion sort, merge sort, quicksort) and the core searching algorithms (linear search, binary search), with emphasis on their time and space complexity. These are among the most exam-tested topics in any introductory CS course.
Sorting rearranges a collection into a defined order. Simple sorts (bubble, insertion) run in O(n²) worst case; efficient sorts (merge sort, quicksort) bring that down to O(n log n). Searching finds a target element: linear search checks every item at O(n), while binary search halves the search space each step at O(log n), but requires sorted input.
Sorting
The process of arranging elements in a particular order, typically ascending or descending. Think of it as alphabetising a bookshelf: you are rearranging items so any title can be found quickly.
Bubble sort
A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass repeats until no swaps are needed. In simple terms, the largest unsorted element "bubbles" to the end of the list on each pass.
Insertion sort
A sorting algorithm that builds the sorted portion of the list one element at a time, picking the next unsorted element and sliding it into its correct position among the already-sorted elements. Think of it as the way most people sort a hand of playing cards: you pick up one card at a time and slot it into the right place.
Merge sort
A divide-and-conquer sorting algorithm that splits the list in half, recursively sorts each half, and then merges the two sorted halves back together. In simple terms, you keep splitting the problem until it is trivially small (a single element), then combine the tiny sorted pieces back up.
Quicksort
A divide-and-conquer sorting algorithm that selects a pivot element, partitions the remaining elements into those less than and greater than the pivot, and recursively sorts the two partitions. Think of it as choosing a reference point and tossing everything smaller to one side and everything larger to the other, then repeating for each side.
Pivot
The element chosen during quicksort's partition step. All other elements are compared against it. Choice of pivot heavily influences quicksort's performance.
Time complexity
A measure of how the running time of an algorithm grows relative to the size of its input, expressed in Big-O notation. In simple terms, it answers: "If I double the input, roughly how much longer will this take?"
Space complexity
A measure of how much additional memory an algorithm requires relative to the size of its input. Think of it as: "How much scratch paper does this algorithm need?"
Linear search (sequential search)
A searching algorithm that checks every element in the collection, one by one, until the target is found or the end is reached. In simple terms, you start at the beginning and look at each item. No shortcuts.
Binary search
A searching algorithm that works on a sorted collection by repeatedly comparing the target to the middle element and discarding the half that cannot contain it. Think of it as the dictionary trick: you open to the middle, see whether your word comes before or after, and ignore the wrong half.
Divide and conquer
An algorithmic strategy that breaks a problem into smaller sub-problems, solves each one independently, and combines the results. Merge sort and quicksort both use this approach.
Stable sort
A sort that preserves the relative order of elements with equal keys. Merge sort and insertion sort are stable; quicksort (in its standard form) and bubble sort's optimised variants may not be.
Sorting takes a collection and rearranges it so elements follow a defined order (numerical, alphabetical, or by a custom key).
Performance is measured by time complexity (how many comparisons/swaps) and space complexity (how much extra memory).
Simple O(n²) sorts are easy to implement and fine for small inputs; O(n log n) sorts are needed as data grows.
Repeatedly compare adjacent pairs and swap if out of order.
After each full pass, the largest unsorted element is in its final position.
Worst and average case: O(n²). Best case (already sorted, with early-exit optimisation): O(n).
Space: O(1), in-place.
Useful for teaching purposes and for detecting nearly-sorted data with the early-exit flag, but rarely used in production.
Maintain a sorted sub-list on the left. Take the next unsorted element and insert it into the correct position within the sorted sub-list.
Worst and average case: O(n²). Best case (already sorted): O(n).
Space: O(1), in-place.
Performs well on small datasets and nearly-sorted data. Many real-world hybrid sorts (like Timsort, used in Python and Java) switch to insertion sort for small sub-arrays.
Divide the list in half recursively until each sub-list has one element.
Merge pairs of sorted sub-lists by comparing their front elements and building a new sorted list.
Worst, average, and best case: O(n log n).
Space: O(n), because the merge step requires a temporary array.
Stable sort. Predictable performance makes it a safe default when worst-case guarantees matter.
Choose a pivot, partition elements into "less than pivot" and "greater than pivot," then recurse on each partition.
Average case: O(n log n). Worst case (bad pivot choices, e.g., already sorted input with first-element pivot): O(n²).
Space: O(log n) for the recursion stack in the average case.
Typically faster than merge sort in practice due to better cache locality and lower constant factors, despite the worse theoretical worst case.
Pivot selection strategies (random pivot, median-of-three) reduce the chance of hitting the worst case.
Start at the first element. Compare each element with the target. Stop when found or when the end of the collection is reached.
Time: O(n) worst and average case. O(1) best case (target is the first element).
Works on unsorted and sorted data alike. No prerequisites on the input.
The fallback when data is unsorted or the collection is too small to justify a more complex approach.
Compare the target with the middle element of a sorted collection.
If they match, you are done.
If the target is smaller, repeat on the left half.
If the target is larger, repeat on the right half.
Time: O(log n). Each comparison eliminates half the remaining elements.
Space: O(1) iterative, O(log n) recursive (call stack).
Precondition: the collection must be sorted. If you need to sort first, the total cost is dominated by the sort (O(n log n) + O(log n) = O(n log n)).
Algorithm | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No* |
*Standard quicksort is not stable. Stable variants exist but add overhead.
Algorithm | Best | Average | Worst | Requires sorted input? |
|---|---|---|---|---|
Linear search | O(1) | O(n) | O(n) | No |
Binary search | O(1) | O(log n) | O(log n) | Yes |
Merge sort's guaranteed O(n log n) behaviour makes it the basis of external sorting (sorting data that does not fit in memory, such as large database tables stored on disk).
Binary search is used constantly: looking up a word in a dictionary app, finding a record in a sorted database index, and locating insertion points in sorted arrays.
Insertion sort is embedded inside many production-grade hybrid algorithms (Timsort, introsort) because it outperforms O(n log n) sorts on tiny sub-arrays where overhead matters more than asymptotic complexity.
"Quicksort is always faster than merge sort." On average, yes, in practice. But quicksort's O(n²) worst case is real and can be triggered by sorted or nearly-sorted input if the pivot is chosen poorly. Merge sort guarantees O(n log n) regardless.
"Binary search works on any list." It requires sorted input. Applying binary search to an unsorted collection gives incorrect results.
"O(n²) algorithms are useless." For very small n (say, under 20 elements), the simplicity and low overhead of insertion sort can beat merge sort or quicksort. That is why hybrid sorts exist.
"Space complexity does not matter for sorting." Merge sort's O(n) extra space can be a problem for very large datasets or memory-constrained environments, which is one reason in-place sorts like quicksort are preferred in practice.
⚠️ Be able to state the best, average, and worst-case time complexity of all four sorting algorithms. This is the single most predictable exam topic.
⚠️ Know when quicksort degrades to O(n²) and how pivot selection mitigates it.
⚠️ Understand that binary search requires sorted input. If a question says "unsorted array," binary search is not applicable without sorting first.
⚠️ Be ready to trace through a small example (5-8 elements) for any of these algorithms, showing the state of the collection after each step or pass.
⚠️ Know the space complexities: merge sort uses O(n) extra space, quicksort uses O(log n) stack space, and the simple sorts are O(1) in-place.
True or false: Bubble sort's best-case complexity is O(n log n).
Fill in the blank: Binary search eliminates _______ of the remaining elements with each comparison.
True or false: Merge sort is an in-place sorting algorithm.
Fill in the blank: Quicksort's worst case occurs when the pivot is consistently the _______ or _______ element.
True or false: Linear search can be applied to unsorted data.
Answers: 1. False (best case is O(n) with the early-exit optimisation). 2. Half. 3. False (it requires O(n) additional space). 4. Smallest, largest (or equivalently, when the partition is maximally unbalanced). 5. True.
Q: Compare the worst-case time complexity of merge sort and quicksort. Which is preferable when worst-case guarantees matter?
A: Merge sort is O(n log n) in all cases. Quicksort can degrade to O(n²) with poor pivot choices. When a worst-case guarantee is required, merge sort is the safer choice.
Q: You have a sorted array of 1,000,000 elements. Roughly how many comparisons does binary search need in the worst case?
A: About 20. log₂(1,000,000) ≈ 19.9. Each comparison halves the search space, so roughly 20 steps suffice.
Q: Why is insertion sort often used inside hybrid sorting algorithms like Timsort, despite being O(n²)?
A: For very small sub-arrays, insertion sort's low overhead and good cache behaviour outperform the recursive overhead of O(n log n) algorithms. The quadratic cost is negligible when n is small (typically under 16-64 elements).
Q: A student uses binary search on an unsorted array and gets an incorrect result. Explain why.
A: Binary search assumes sorted order to decide which half to discard. If the array is unsorted, the comparison with the middle element does not reliably indicate which half contains the target, so the algorithm may discard the half that holds the answer.
Q: Describe one scenario where bubble sort might be a reasonable choice.
A: When the data is already nearly sorted and you add the early-exit optimisation (stop if a full pass produces no swaps). In that case, bubble sort can finish in O(n) time and uses no extra space.
Sorting is a prerequisite for binary search and for many algorithms that assume ordered input, such as two-pointer techniques and interval merging.
Merge sort's divide-and-conquer pattern appears throughout algorithms: it is the same strategy behind the fast Fourier transform, closest-pair algorithms, and Strassen's matrix multiplication.
Searching connects directly to hash tables (O(1) average lookup) and balanced binary search trees (O(log n) lookup), both of which you will study next as alternatives to binary search on a flat array.
sorting algorithms, searching algorithms, bubble sort, insertion sort, merge sort, quicksort, linear search, binary search, sequential search, time complexity, space complexity, Big-O, O(n²), O(n log n), O(log n), divide and conquer, pivot, partition, stable sort, in-place sort, comparison sort, Timsort, introsort, CS101, UCF, Computer Science I, intro to algorithms, exam review