Sorting · 153Medium
Sort an Array
Given an array nums, sort it in ascending order WITHOUT using any built-in sort. The solution must run in O(n log n) time and use the smallest space possible.
Constraints
- 1 <= nums.length <= 5 * 10^4
- -5 * 10^4 <= nums[i] <= 5 * 10^4
Examples
sortArray([5, 2, 3, 1]) -> [1, 2, 3, 5] sortArray([5, 1, 1, 2, 0, 0]) -> [0, 0, 1, 1, 2, 5] sortArray([1]) -> [1] // single element sortArray([1, 2, 3, 4]) -> [1, 2, 3, 4] // already sorted sortArray([4, 3, 2, 1]) -> [1, 2, 3, 4] // reverse sorted sortArray([-5, 3, -5, 0, 2]) -> [-5, -5, 0, 2, 3] // negatives, zero and duplicates
Edge cases
- Duplicates must be preserved, not collapsed.
- Already-sorted or reverse-sorted input.
Show the target complexity (spoiler)
- Naive
- O(n^2) time — bubble, selection or insertion sort. Fine to write once for
- Target
- O(n log n) time — merge sort (O(n) space, stable, predictable) or heapsort (O(1) space). This is the problem for actually IMPLEMENTING a sort.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/20-sorting/153-sort-an-array.js ./practice c 153