912. Sort an Array

Problem Link

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

---

C++

class Solution {
public:
    void mergeSort(int i, int j, vector<int>& nums) {
        if (i >= j) return;
 
        int mid = (i + j) / 2;
        mergeSort(i, mid, nums);
        mergeSort(mid + 1, j, nums);
        merge(i, mid, j, nums);
    }
 
    void merge(int i, int mid, int j, vector<int>& nums) {
        if (i >= j) return;
        int l = i, r = mid + 1, k = 0, size = j - i + 1;
        vector<int> sorted(size);
 
        while (l <= mid && r <= j)
            sorted[k++] = nums[l] < nums[r] ? nums[l++] : nums[r++];
        
        while (l <= mid)
            sorted[k++] = nums[l++];
        
        while (r <= j)
            sorted[k++] = nums[r++];
        
        for (k = 0; k < size; k++)
            nums[k + i] = sorted[k];
    }
 
    vector<int> sortArray(vector<int>& nums) {
       int N = nums.size();
 
       mergeSort(0, N - 1, nums);
 
       return nums;
    }
};

Python3

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        N = len(nums)
 
        def merge(left, right):
            L, R = len(left), len(right)
            s = []
            i = j = 0
 
            while i < L or j < R:
                if i < L and j < R:
                    if left[i] < right[j]:
                        s.append(left[i])
                        i += 1
                    else:
                        s.append(right[j])
                        j += 1
                else:
                    if i < L:
                        s.append(left[i])
                        i += 1
                    else:
                        s.append(right[j])
                        j += 1
 
            return s
 
        def mergeSort(i, j):
            if i == j: return [nums[i]]
 
            mid = (i + j) // 2
 
            left = mergeSort(i, mid)
            right = mergeSort(mid + 1, j)
 
            return merge(left, right)
        
        return mergeSort(0, N - 1)