Efficient Solution for Sorting an Array in 𝑂(𝑛 log ⁡ 𝑛) Time Complexity
If you found this solution helpful, please upvote! \uD83D\uDE0A\n\n# Intuition\nThe problem requires sorting an array in ascending order with optimal time and s
# **If you found this solution helpful, please upvote! \uD83D\uDE0A**\n\n# Intuition\nThe problem requires sorting an array in ascending order with optimal time and space complexity. Given the constraints, the Merge Sort algorithm is a suitable choice because it divides the array into smaller subarrays, sorts them, and merges them efficiently. This approach make sures that we maintain a time complexity of \uD835\uDC42(\uD835\uDC5B log \uD835\uDC5B), which is ideal for this problem.\n\n# Approach\nWe use the Merge Sort algorithm to solve this problem. First, we define a **merge** function to combine two sorted subarrays into a single sorted subarray using a temporary array. The **mergeSort** function recursively divides the array into smaller subarrays until each subarray contains a single element. After sorting the subarrays, we merge them back together. Finally, the **sortArray** function initializes the temporary array, invokes **mergeSort** on the entire array, and returns the sorted array.\n\n# Complexity\n- Time complexity - \uD835\uDC42(\uD835\uDC5B log \uD835\uDC5B)\n- Space complexity - \uD835\uDC42(\uD835\uDC5B)\n# Code\n```\nclass Solution {\npublic:\n    void merge(vector<int>& nums, int left, int mid, int right, vector<int>& temp) {\n        int lSize = mid - left + 1, rSize = right - mid, lIdx = 0, rIdx = 0, k = left;\n        for (int i{0}; i < lSize; ++i) {\n            temp[i] = nums[left + i];\n        }\n        while (lIdx < lSize && rIdx < rSize) {\n            if (temp[lIdx] <= nums[mid + 1 + rIdx]) nums[k++] = temp[lIdx++];\n            else nums[k++] = nums[mid + 1 + rIdx++];\n        }\n        while (lIdx < lSize) {\n            nums[k++] = temp[lIdx++];\n        }\n    }\n    void mergeSort(vector<int>& nums, int left, int right, vector<int>& temp) {\n        if (left >= right) return;\n        int mid = left + (right - left) / 2;\n        mergeSort(nums, left, mid, temp);\n        mergeSort(nums, mid + 1, right, temp);\n        merge(nums, left, mid, right, temp);\n    }\n    vector<int> sortArray(vector<int>& nums) {\n        vector<int> temp(nums.size());\n        mergeSort(nums, 0, nums.size() - 1, temp);\n        return nums;\n    }\n};\n```\nThis implementation achieves \uD835\uDC42(\uD835\uDC5B log \u2061\uD835\uDC5B)time complexity with \uD835\uDC42(\uD835\uDC5B)auxiliary space due to the temporary arrays used for merging. \nFeel free to ask any questions or provide feedback.
['C++']