SeniorCodeRareNot answered yet
Implement merge sort or introsort with correctness discussion
Implement an O(n log n)-guaranteed sort of the vector in-place (e.g. bottom-up merge sort or an introsort-style hybrid). Be ready to justify when you would pick it over quicksort or heapsort.
Requirements:
- Worst-case O(n log n) — no degradation to O(n²) on adversarial input.
- State whether your choice is stable and what extra space it uses.
- Handle empty, single-element, and duplicate-heavy inputs.
#include <vector>
void sort(std::vector<int>& arr) {
// your code here
}Write the implementation.
Merge sort guarantees O(n log n) and is stable, making it suitable for linked lists and external sorting. Introsort (quicksort + heapsort fallback + insertion sort for small ranges) is what std::sort uses: O(n log n) guaranteed, in-place, but not stable.
- ✗Not knowing why
std::sortuses introsort instead of pure quicksort - ✗Implementing merge sort with O(n log n) extra space when an in-place version is asked
- ✗Ignoring the insertion sort optimisation for small subarrays (< 16 elements)
- →What is the depth threshold at which introsort switches from quicksort to heapsort?
- →How does
std::stable_sortdiffer fromstd::sortin terms of algorithm and complexity?
Contents
Task
Implement bottom-up merge sort (iterative, no recursion) and discuss algorithm selection.
Key points
- Bottom-up merge sort: iterative, O(n log n) guaranteed, stable, O(n) extra space.
- Introsort = quicksort + heapsort fallback + insertion sort for small ranges — used by
std::sort. - Choose merge sort when stability is required or data is in a linked list.
- Timsort (Python, Java) exploits natural runs in real-world data.
Contents
