Sort an Array
Medium · Arrays & Hashing · Array · Divide and Conquer · Sorting · Heap (Priority Queue) · Merge Sort
Problem
You are given an integer array nums. Sort it in ascending order and return it.
You must not use any built-in sort function. Your algorithm should run in O(n log n) time and use as little extra space as possible, which makes merge sort, heap sort, or a randomized quicksort good choices. Plain quicksort with a fixed pivot can degrade to O(n^2) on sorted or all-equal inputs, so be careful with pivot choice and duplicate handling.
Examples
Input: nums = [4,-1,7,0,-1] Output: [-1,-1,0,4,7]
Duplicates stay next to each other in the sorted output.
Input: nums = [3,3,3] Output: [3,3,3]
All values are equal, so nothing moves.
Input: nums = [10,9,8,1] Output: [1,8,9,10]
A reverse-sorted input comes out ascending.
Constraints
- 1 <= len(nums) <= 5 · 10^4
- -5 · 10^4 <= nums[i] <= 5 · 10^4
Approaches
- Insertion sort — time O(n²), space O(1)
Follow-up
The values lie in [-5 · 10^4, 5 · 10^4], only 10^5 possible values. Counting sort (count each value, then write them out in order) runs in O(n + range) without comparing anything, which beats O(n log n) here. Comparison sorts cannot do better than O(n log n) in general, but a known small range changes the rules.
Related problems
Start free on Cariara · Coding problems · System design studio
