213. Sort It Yourself
You are given an array of integers nums. Return the same numbers arranged in ascending order. Duplicates must be kept, so [4, 4, 1] becomes [1, 4, 4].
The point of this exercise is to write the sorting algorithm yourself. Please do not use the sort function of your language's standard library. The platform cannot check this automatically, but your solution will be much more valuable to you if you build it from scratch. Your algorithm should run in O(n log n) time: the array can contain 50,000 numbers, and simple quadratic methods like bubble or insertion sort will be too slow.
Hint for the spirit of the task: think of how two already sorted lists can be combined into one sorted list.
Example 1
- Input:
- nums = [34,-5,12,12,0]
- Output:
- [-5,0,12,12,34]
- Explanation:
Sorted ascending, keeping both 12s: -5, 0, 12, 12, 34.
Example 2
- Input:
- nums = [17]
- Output:
- [17]
- Explanation:
A single number is already sorted.
Example 3
- Input:
- nums = [9,8,7,6]
- Output:
- [6,7,8,9]
- Explanation:
A descending array is reversed.
Constraints
1 ≤ nums.length ≤ 5 × 104
-109 ≤ nums[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)