551. Sort an Array
You are given an integer array nums. Return the same numbers arranged in non-decreasing order (smallest first; equal values may sit next to each other).
The catch: do it without calling your language's built-in sort. The goal is to implement an O(n log n) sorting algorithm yourself — merge sort, heapsort, or a well-behaved quicksort — and to understand what it costs in time and extra memory.
Duplicates and negative numbers both appear, so your algorithm has to handle them cleanly.
Example 1:
Input: nums = [5, 2, 3, 1]
Output: [1, 2, 3, 5]
Explanation: Arranged from smallest to largest, 5 2 3 1 becomes 1 2 3 5.
Example 2:
Input: nums = [5, 1, 1, 2, 0, 0]
Output: [0, 0, 1, 1, 2, 5]
Explanation: Duplicates are kept — both 0s and both 1s appear in the output, just grouped together.
Constraints:
- 1 ≤ nums.length ≤ 5 * 10⁴
- -5 * 10⁴ ≤ nums[i] ≤ 5 * 10⁴
- Implement the sort yourself — no built-in sort calls.
Hints:
A quadratic sort (insertion, selection, bubble) is easy to write and a good warm-up, but at n = 5·10^4 it does over a billion comparisons. You need the divide-and-conquer jump to n log n.
Merge sort's insight: sorting a whole array is hard, but merging two already-sorted halves is a single linear pass with two fingers. Split in half, sort each half recursively, merge.
The values live in a small fixed range (−5·10^4 … 5·10^4). What could you do with a tally of how many times each value occurs?
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [5, 2, 3, 1]
Expected output: [1, 2, 3, 5]