Sort an Array
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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)
