🔍 Searching and Sorting Algorithms in C++ — Linear, Binary, Bubble, Merge, Quick
Master searching and sorting algorithms in C++ — linear & binary search, bubble, selection, insertion, merge and quick sort. Complexity analysis + interview-ready code.
Every CS curriculum drills these — they're the bread and butter of interview rounds.
🔍 Searching
- Linear search — O(n). Walk through, compare each.
- Binary search — O(log n). Requires a SORTED input. Halve the range each step.
🔃 Sorting — quick reference
| Algorithm | Best | Avg | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
💡 What's stable mean?
A sort is stable if it preserves the original order of equal-keyed elements. Crucial when sorting by multiple keys.
📚 In practice
std::sort uses introsort — quicksort + heapsort fallback for worst case. std::stable_sort uses merge sort. std::binary_search exists for searching.
💻 Code Examples
Binary search (sorted array)
int binarySearch(int arr[], int n, int target) {
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}Output:
O(log n). Use `lo + (hi-lo)/2` to avoid integer overflow.
Bubble sort
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j+1])
std::swap(arr[j], arr[j+1]);
}Output:
Simple. O(n²) — only educational; never use in production.
Quick sort (Lomuto partition)
int partition(int a[], int lo, int hi) {
int pivot = a[hi]; int i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] <= pivot) std::swap(a[++i], a[j]);
std::swap(a[i+1], a[hi]);
return i + 1;
}
void quickSort(int a[], int lo, int hi) {
if (lo < hi) {
int p = partition(a, lo, hi);
quickSort(a, lo, p - 1);
quickSort(a, p + 1, hi);
}
}Output:
Average O(n log n). Worst case O(n²) with bad pivots.
⚠️ Common Mistakes
- Binary search with `mid = (lo + hi) / 2` overflowing for large indices — use `lo + (hi - lo) / 2`.
- Forgetting that binary search needs SORTED input.
- Calling `std::sort` then `std::binary_search` with a different comparator — UB.
- Picking quicksort on already-sorted/reverse-sorted data with naive pivot — O(n²).
🎯 Interview Questions
Real questions asked at top product and service-based companies.
Q1.What's the difference between linear search and binary search?Beginner
Linear: walk through, compare each — O(n), works on any input. Binary: halve the range each step — O(log n), but requires the input to be SORTED.
Q2.What's a stable sort and why does it matter?Intermediate
A sort that preserves the original relative order of equal-keyed elements. Matters when sorting by multiple keys in sequence — e.g., sort by lastName, then by department: stable sort keeps lastName order within departments.
Q3.What's the complexity of merge sort?Intermediate
O(n log n) in all cases (best, average, worst). Space: O(n) auxiliary. Stable. Used for sorting linked lists and external data because it's predictable.
Q4.What's the worst-case complexity of quick sort, and how do we mitigate it?Advanced
O(n²) when the pivot is the smallest or largest each time (e.g., already-sorted input with first-element pivot). Mitigations: random pivot, median-of-three pivot, switch to heapsort below a depth threshold (introsort).
Q5.What does std::sort use under the hood?Advanced
Typically introsort — quicksort by default, switches to heapsort if recursion depth exceeds a threshold (guaranteeing O(n log n)), and insertion sort for small subarrays. Combines speed with worst-case safety.
🧠 Quick Summary
- Linear search O(n); binary search O(log n) on sorted input.
- Bubble/Selection/Insertion: O(n²) — educational only.
- Merge sort: O(n log n) stable, O(n) space.
- Quick sort: O(n log n) avg, O(n²) worst — fast in practice.
- std::sort uses introsort; std::stable_sort uses merge sort.
- Pick stable when sorting by multiple keys.