Statement▼
Given an integer array, nums, sort it in ascending order and return the sorted array.
You must implement the sorting algorithm yourself; do not use any built-in sorting functions. The solution must run in
O(nlogn) time and use the minimum possible extra space.
Constraints:
1≤ nums.length≤103 −103≤ nums[i]≤103
Solution
The problem requires sorting an array in ascending order with
Merge sort: It guarantees
O(nlogn) time complexity in all cases. Its space complexity isO(n) due to the auxiliary array needed for merging. Even though the space complexity is notO(1) , it is a common and robust approach for sorting.Quick sort: On average, it achieves
O(nlogn) time complexity andO(logn) space complexity (for the recursion stack), making it very efficient. It’s often an in-place sort. However, its worst-case time complexity isO(n2) , which is not promising if not implemented carefully with good pivot selection, potentially failing theO(nlogn) requirement under specific input distributions.Heap sort: It offers
O(nlogn) time complexity in all cases andO(1) space complexity, making it an excellent choice for strict space requirements. It’s an in-place sorting algorithm.
Given the explicit requirement for minimum space complexity possible and a guaranteed
In the solution with heap sort, the input array, nums, is first converted into a max heap, so the largest element is always at the root (the first position of the array). Once the max heap is built, the algorithm repeatedly swaps the root with the last element of the max heap, effectively moving the largest value to its correct position at the end. After each swap, the heap size is reduced by one, and the remaining elements are restructured to maintain the heap property. This process continues until all elements are placed in order, producing a sorted array in ascending order.