Sort an Array

The key idea

A quadratic sort like insertion sort is simple but does ~n^2/2 comparisons, so it times out near n = 5 * 10^4. To hit O(n log n) you must split the work: sort two halves and merge them in linear time, or repeatedly sink the largest element with a binary heap. Merge sort is the safe pick — it is always O(n log n) and stable, at the cost of an O(n) scratch buffer.

Problem

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in O(n log(n)) time complexity and with the smallest space complexity possible.

Constraints

1 <= nums.length <= 5 * 10^4
-5 * 10^4 <= nums[i] <= 5 * 10^4

Examples

Input: nums = [5,2,3,1] Output: [1,2,3,5]

Input: nums = [5,1,1,2,0,0] Output: [0,0,1,1,2,5]

Complexity

Time: O(n log n) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →