JuniorCodeVery commonNot answered yet
Implement a sorting algorithm
Implement a comparison sort that orders the vector in ascending order in-place. Pick one algorithm (e.g. quicksort or merge sort) and be ready to discuss its complexity and stability.
Requirements:
- Average O(n log n).
- Handle the base cases (size 0 and size 1) and duplicate elements.
- Do not call
std::sort— implement the algorithm yourself.
#include <vector>
void sort(std::vector<int>& arr) {
// your code here
}Write the implementation.
Quicksort: average O(n log n), in-place, not stable, degrades to O(n²) on bad pivots — use median-of-three or random pivot. Merge sort: guaranteed O(n log n), stable, requires O(n) extra space.
- ✗Always choosing the first element as pivot — O(n²) on sorted input
- ✗Not handling the base case (array of size 0 or 1)
- ✗Confusing merge sort stability with quicksort's in-place property
- →What is introsort and why does
std::sortuse it instead of pure quicksort? - →When would you choose merge sort over quicksort?
Contents
Task
Implement quicksort and merge sort.
Key points
- Quicksort: in-place, fast in practice, O(n²) worst case without good pivot selection.
- Merge sort: guaranteed O(n log n), stable, but needs O(n) extra space.
- In production always use
std::sort(introsort = quicksort + heapsort + insertion sort).
Contents
