912. Leetcode Solution in cpp

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

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/