Sort an Array
Problem
Sort an integer array in ascending order without calling a built-in sort. The solution must run in O(n log n) time and should use as little extra space as practical.
Examples
Constraints
- • 1 <= nums.length <= 5 * 10^4
- • -5 * 10^4 <= nums[i] <= 5 * 10^4
Hints & approach
Hint 1
Simple quadratic sorts (bubble, insertion) will time out.
Hint 2
Merge sort guarantees O(n log n) regardless of input order.
Hint 3
Quicksort with a fixed pivot can degrade to O(n^2) on adversarial input; randomise the pivot or use heap sort.
Approachtry the hints first
Implement merge sort: split the array in half, sort each half recursively, then merge the two sorted halves with two pointers into a buffer. The recursion depth is log n and each level does linear work, giving O(n log n) in all cases. Heap sort is an O(1)-space alternative, and randomised quicksort is fast in practice but only O(n log n) in expectation.
Time O(n log n) · Space O(n)