Sorting orders elements so binary search and two-pointer techniques apply. Comparison sorts target O(n log n); know when stability matters.
Built-in sort
std::sort on vectors—O(n log n) average. std::stable_sort preserves equal-element order.
Conceptual complexities
- Bubble / insertion — O(n²), educational
- Merge sort — O(n log n), stable, extra space
- Quick sort — O(n log n) average, in-place partition
Sort then scan
#include
#include
#include
int main() {
std::vector a = {5, 1, 4, 2, 8};
std::sort(a.begin(), a.end());
for (int x : a) std::cout << x << " ";
std::cout << "\n";
return 0;
} Important interview questions and answers
- Q: Stable sort meaning?
A: Equal keys keep original relative order—important for sorting by multiple keys. - Q: Sort before binary search?
A: Binary search requires sorted data—O(n log n) sort + O(log n) search.
Self-check
- What is typical complexity of std::sort?
- When use stable_sort?
Tip: Sorting unlocks binary search and two pointers—O(n log n) preprocessing trade.
Interview prep
- Why sort?
Enables binary search, two pointers, duplicate grouping.
- Stable sort?
Preserves order of equal keys—stable_sort in C++.