DataslopeEfficient Sorting Algorithms
Learn merge sort, quicksort, std::sort, std::stable_sort, custom comparators, and stability trade-offs in C++
Efficient sorting algorithms reduce the cost from O(n^2) to O(n log n) for large inputs. They rely on divide and conquer, partitioning, and hybrid engineering.
Merge sort
Merge sort divides the array in half, recursively sorts each half, then merges the sorted halves. It guarantees O(n log n) time, uses O(n) extra memory, and is stable when merging prefers the left element on ties.
mergeSort(a): if size <= 1 return; sort left; sort right; mergeQuicksort
Quicksort chooses a pivot, partitions values around it, then recursively sorts both sides. It is in-place and O(n log n) on average, but O(n^2) in the worst case with bad pivots. This version uses Lomuto partition.
Pivot strategy matters
Naive quicksort can degrade to O(n^2). Random pivots and median-of-three pivots reduce the chance of consistently bad partitions.
std::sort
Prefer std::sort unless you specifically need stability. It is an introsort-style hybrid: quicksort for speed, heapsort fallback to avoid quadratic worst cases, and insertion sort for tiny ranges.
std::stable_sort and comparators
Use std::stable_sort when equal keys must keep their original relative order. A comparator returns true when the first argument should come before the second.
Sorting std::pair values by their second field is a common lambda example.
Practice: implement merge sort
Implement void mergeSort(std::vector<int>& v). The driver sorts {5,2,8,1,9,3,7,4} and prints each value on its own line.
Practice: sort pairs by score
Sort the given std::vector<std::pair<std::string,int>> by the integer value in descending order, then print each pair as name=value.
Check your understanding
Which statement best compares merge sort and naive quicksort worst-case time?
Merge sort can be O(n^2), while quicksort is always O(n log n).
Merge sort guarantees O(n log n), while naive quicksort can be O(n^2).
Both are always O(n^2).
Both require O(n) extra arrays in standard forms.
What strategy does std::sort commonly use in modern C++ implementations?
Pure bubble sort
Pure merge sort only
Introsort: quicksort-style partitioning with safeguards and small-range optimizations
Linear search followed by insertion
When does sort stability matter most?
When all elements are distinct integers.
When sorting descending instead of ascending.
When equal keys should preserve their previous relative order.
When the vector is stored contiguously.