The problem
Sort an integer array in O(n log n) without built-in sort functions — the judge’s adversarial inputs kill naive quicksort.
Stuck? Reveal hints one at a time
How to approach it
- 1Merge sort: recursively split the array into halves until size 1.
- 2Merge two sorted halves with two pointers into a temp buffer.
- 3Copy back. Recursion depth log n, each level O(n) merging.
Key insight
This problem exists to teach the difference between average-case and worst-case: unrandomized quicksort TLEs here by design.
The solution
Watch out for
- Plain quicksort with first/last pivot hits O(n²) on the sorted-input tests — randomize or switch algorithms.
- Use <= in the merge for stability.