C++ and Python3 || Merge Sort || Simple and Optimal
\n# Complexity\n- Time complexity: O(nlogn)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(n)\n Add your space complexity here, e.g. O(n) 
\n# Complexity\n- Time complexity: $$O(nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    void merge(vector<int> &arr, int low, int mid, int high) {\n        vector<int> res(high - low + 1);\n        int i = low, j = mid + 1, k = 0;\n        while(i <= mid && j <= high) {\n            if(arr[i] <= arr[j]) res[k++] = arr[i++];\n            else res[k++] = arr[j++];\n        }\n        while(i <= mid) res[k++] = arr[i++];\n        while(j <= high) res[k++] = arr[j++];\n        for(int x = 0; x < res.size(); x++) {\n            arr[low + x] = res[x];\n        }\n    }\n\n    void mergeSort(vector<int> &arr, int low, int high) {\n        if(low < high) {\n            int mid = low + (high - low) / 2;\n            mergeSort(arr, low, mid);\n            mergeSort(arr, mid + 1, high);\n            merge(arr, low, mid, high);\n        }\n    }\n\n    vector<int> sortArray(vector<int>& nums) {\n        mergeSort(nums, 0, nums.size() - 1);\n        return nums;\n    }\n};\n```\n```Python3 []\nclass Solution:\n    def sortArray(self, nums: List[int]) -> List[int]:\n        def merge(low, mid, high):\n            res = [0] * (high - low + 1)\n            i = low\n            j = mid + 1\n            k = 0\n            while i <= mid and j <= high:\n                if nums[i] <= nums[j]:\n                    res[k] = nums[i]\n                    i += 1\n                    k += 1\n                else:\n                    res[k] = nums[j]\n                    j += 1\n                    k += 1\n            while i <= mid:\n                res[k] = nums[i]\n                i += 1\n                k += 1\n            while j <= high:\n                res[k] = nums[j]\n                j += 1\n                k += 1\n            for x in range(len(res)):\n                nums[low + x] = res[x]\n        def mergeSort(low, high):\n            if low < high:\n                mid = low + (high - low) // 2\n                mergeSort(low, mid)\n                mergeSort(mid + 1, high)\n                merge(low, mid, high)\n        mergeSort(0, len(nums) - 1)\n        return nums\n```
['Sorting', 'Merge Sort', 'C++', 'Python3']