Sort an Array

Sort an Array: the approach in brief

The problem

Given nums, an array of integers, arrange all of its elements in ascending order. Ascending order means each element is less than or equal to the element that follows it, so duplicate values remain present with the same frequency.

Pattern

Sort an Array is a Greedy Patterns problem, in the Sorting Based subpattern. The pattern covers interval scheduling, jump games, stock trading, and task scheduling

Approach outline

1. Consider dividing the array into smaller ranges until each range has at most one element.
2. Once two neighboring ranges are sorted, they can be combined by repeatedly choosing the smaller front element.
3. Apply the combine operation while the ranges are being rebuilt, rather than sorting each range with a library routine.

Complexity

The reference solution runs in O(n log n) time and O(n) auxiliary space, plus O(log n) recursion stack space.