Sort Integers in Ascending Order with Constant Auxiliary Storage
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Return `nums` in ascending order, retaining every occurrence. Implement the sorting procedure yourself, without a built-in sorting routine, in O(n log n) time and with the smallest auxiliary storage possible.
```cpp
class Solution {
public:
vector<int> sortArray(vector<int>& nums);
};
```
### Examples
**Example 1:**
```text
Input: nums = [4,-2,4,0]
Output: [-2,0,4,4]
Explanation: Negative values and both occurrences of4 are retained in nondecreasing order.
```
**Example 2:**
```text
Input: nums = [9,3,7]
Output: [3,7,9]
Explanation: All three values appear in ascending order.
```
### Constraints
- `1 <= nums.length <= 5*10^4`.
- `-5*10^4 <= nums[i] <= 5*10^4`.
### Contract considerations
No library sort, heap-construction, or heap-extraction routine is used. The implementation performs comparisons and explicit value exchanges.
```hint Read the boundary condition
Can the array hold both the working heap and the completed sorted suffix?
```
### Boundary reminders
No library sort, heap-construction, or heap-extraction routine is used. The implementation performs comparisons and explicit value exchanges.
Overview: Sort Integers in Ascending Order with Constant Auxiliary Storage. Return nums in ascending order, retaining every occurrence.