===========================================================

Description:

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(nlog(n)) time complexity and with the smallest space complexity possible.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).
Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessairly unique.

Constraints:

1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104

===========================================================

Solution:

class Solution { public: vector<int> sortArray(vector<int>& nums) { mergeSort(nums, 0, nums.size() - 1); return nums; } private: void mergeSort(vector<int>& A, int l, int r) { if (l >= r) return; const int m = (l + r) / 2; mergeSort(A, l, m); mergeSort(A, m + 1, r); merge(A, l, m, r); } void merge(vector<int>& A, int l, int m, int r) { vector<int> sorted(r - l + 1); int k = 0; // sorted's index int i = l; // left's index int j = m + 1; // right's index while (i <= m && j <= r) if (A[i] < A[j]) sorted[k++] = A[i++]; else sorted[k++] = A[j++]; // put possible remaining left part to the sorted array while (i <= m) sorted[k++] = A[i++]; // put possible remaining right part to the sorted array while (j <= r) sorted[k++] = A[j++]; copy(begin(sorted), end(sorted), begin(A) + l); } }; 

leetcode

challenge

Here is the link for the problem:
https://leetcode.com/problems/sort-an-array/