💯✅🔥Detailed Easy Java ,Python3 ,C++ Solution|| 25 ms ||≧◠‿◠≦✌
Intuition\n\nMerge Sort is a divide-and-conquer algorithm that recursively divides the input array into smaller subarrays until they are small enough to sort. I
# Intuition\n\nMerge Sort is a divide-and-conquer algorithm that recursively divides the input array into smaller subarrays until they are small enough to sort. It then merges these sorted subarrays back together to form the final sorted array.\n\n---\n# Approach\n\nThe code consists of three main methods:\n\n1. `sortArray(int[] nums)`: This is the main entry point that takes an unsorted array `nums` as input and returns the sorted array.\n\n2. `mergeSort(int[] arr, int s, int e)`: This method performs the recursive division of the array. It takes an array `arr` and the start and end indices `s` and `e`, respectively. If the subarray has only one element (`e-s == 1`), it returns. Otherwise, it recursively calls `mergeSort` on the left and right halves of the subarray and then merges the sorted subarrays using the `merge` method.\n\n3. `merge(int[] arr, int s, int m, int e)`: This method merges two sorted subarrays `arr[s:m]` and `arr[m:e]` into a single sorted subarray. It uses three pointers `i`, `j`, and `k` to iterate through the left subarray, right subarray, and the merged subarray, respectively. It compares the elements from the left and right subarrays and adds the smaller element to the merged subarray. Finally, it copies the merged subarray back into the original array.\n\n---\n# Time Complexity\n\nThe time complexity of Merge Sort is O(n log n), where n is the size of the input array. This is because the algorithm recursively divides the array into halves and merges the sorted subarrays, which takes O(n) time per merge operation. The number of merge operations is proportional to the height of the recursion tree, which is log n.\n\n---\n# Space Complexity\n\nThe space complexity of Merge Sort is O(n), where n is the size of the input array. This is because the algorithm needs to create a temporary array of size n to store the merged elements during the merge operation.\n\nIn the provided code, the commented line `System.arraycopy(mix, 0, arr, 0, mix.length);` can be used to copy the merged subarray back into the original array. However, the code below it, which uses a for loop to copy the elements, achieves the same result and is more concise.\n\n---\n\nLet\'s walk through the Merge Sort algorithm step by step using the input array `[5, 1, 1, 2, 0, 0]`. We will illustrate how the algorithm divides the array and merges the sorted subarrays.\n\n### Initial Call\n\n1. **Input Array**: `[5, 1, 1, 2, 0, 0]`\n2. **Function Call**: `sortArray(nums)` which calls `mergeSort(nums, 0, nums.length)` or `mergeSort(nums, 0, 6)`.\n\n### Step 1: First Level of Recursion\n\n- **Current Array**: `[5, 1, 1, 2, 0, 0]`\n- **Indices**: `s = 0`, `e = 6`\n- **Middle Index**: `m = 0 + (6 - 0) / 2 = 3`\n\n#### Split into Two Halves\n- Left Half: `[5, 1, 1]` (indices 0 to 3)\n- Right Half: `[2, 0, 0]` (indices 3 to 6)\n\n### Step 2: Second Level of Recursion (Left Half)\n\n- **Current Array**: `[5, 1, 1]`\n- **Indices**: `s = 0`, `e = 3`\n- **Middle Index**: `m = 0 + (3 - 0) / 2 = 1`\n\n#### Split into Two Halves\n- Left Half: `` (indices 0 to 1)\n- Right Half: `[1, 1]` (indices 1 to 3)\n\n### Step 3: Third Level of Recursion (Left Half of Left Half)\n\n- **Current Array**: ``\n- **Indices**: `s = 0`, `e = 1`\n- Since `e - s = 1`, we return without further splitting.\n\n### Step 4: Third Level of Recursion (Right Half of Left Half)\n\n- **Current Array**: `[1, 1]`\n- **Indices**: `s = 1`, `e = 3`\n- **Middle Index**: `m = 1 + (3 - 1) / 2 = 2`\n\n#### Split into Two Halves\n- Left Half: `` (indices 1 to 2)\n- Right Half: `` (indices 2 to 3)\n\n### Step 5: Fourth Level of Recursion (Left Half of Right Half)\n\n- **Current Array**: ``\n- **Indices**: `s = 1`, `e = 2`\n- Since `e - s = 1`, we return.\n\n### Step 6: Fourth Level of Recursion (Right Half of Right Half)\n\n- **Current Array**: ``\n- **Indices**: `s = 2`, `e = 3`\n- Since `e - s = 1`, we return.\n\n### Step 7: Merging the Left Half\n\nNow we merge the two sorted halves `` and `[1, 1]`:\n\n- **Merge Call**: `merge(arr, 0, 1, 3)`\n- **Current State**: \n  - Left Array: `` (indices 0 to 1)\n  - Right Array: `[1, 1]` (indices 1 to 3)\n- **Merged Result**: \n  - Compare `5` and `1`: `1` is smaller, add `1` to the mix.\n  - Compare `5` and `1`: `1` is smaller again, add `1` to the mix.\n  - Add remaining `5` to the mix.\n- **Merged Array**: `[1, 1, 5]`\n\n### Step 8: Second Level of Recursion (Right Half)\n\nNow we process the right half `[2, 0, 0]`:\n\n- **Current Array**: `[2, 0, 0]`\n- **Indices**: `s = 3`, `e = 6`\n- **Middle Index**: `m = 3 + (6 - 3) / 2 = 4`\n\n#### Split into Two Halves\n- Left Half: `` (indices 3 to 4)\n- Right Half: `[0, 0]` (indices 4 to 6)\n\n### Step 9: Third Level of Recursion (Left Half of Right Half)\n\n- **Current Array**: ``\n- **Indices**: `s = 3`, `e = 4`\n- Since `e - s = 1`, we return.\n\n### Step 10: Third Level of Recursion (Right Half of Right Half)\n\n- **Current Array**: `[0, 0]`\n- **Indices**: `s = 4`, `e = 6`\n- **Middle Index**: `m = 4 + (6 - 4) / 2 = 5`\n\n#### Split into Two Halves\n- Left Half: `` (indices 4 to 5)\n- Right Half: `` (indices 5 to 6)\n\n### Step 11: Fourth Level of Recursion (Left Half of Right Half)\n\n- **Current Array**: ``\n- **Indices**: `s = 4`, `e = 5`\n- Since `e - s = 1`, we return.\n\n### Step 12: Fourth Level of Recursion (Right Half of Right Half)\n\n- **Current Array**: ``\n- **Indices**: `s = 5`, `e = 6`\n- Since `e - s = 1`, we return.\n\n### Step 13: Merging the Right Half\n\nNow we merge the two sorted halves `` and `[0, 0]`:\n\n- **Merge Call**: `merge(arr, 3, 4, 6)`\n- **Current State**: \n  - Left Array: `` (indices 3 to 4)\n  - Right Array: `[0, 0]` (indices 4 to 6)\n- **Merged Result**: \n  - Compare `2` and `0`: `0` is smaller, add `0` to the mix.\n  - Compare `2` and `0`: `0` is smaller again, add `0` to the mix.\n  - Add remaining `2` to the mix.\n- **Merged Array**: `[0, 0, 2]`\n\n### Step 14: Final Merge\n\nFinally, we merge the two sorted halves `[1, 1, 5]` and `[0, 0, 2]`:\n\n- **Merge Call**: `merge(arr, 0, 3, 6)`\n- **Current State**: \n  - Left Array: `[1, 1, 5]` (indices 0 to 3)\n  - Right Array: `[0, 0, 2]` (indices 3 to 6)\n- **Merged Result**: \n  - Compare `1` and `0`: `0` is smaller, add `0` to the mix.\n  - Compare `1` and `0`: `0` is smaller again, add `0` to the mix.\n  - Compare `1` and `2`: `1` is smaller, add `1` to the mix.\n  - Compare `1` and `2`: `1` is smaller again, add `1` to the mix.\n  - Add remaining `5` to the mix.\n- **Final Sorted Array**: `[0, 0, 1, 1, 2, 5]`\n\n### Conclusion\n\nThe Merge Sort algorithm successfully sorts the array `[5, 1, 1, 2, 0, 0]` into `[0, 0, 1, 1, 2, 5]` through a series of recursive splits and merges. This step-by-step breakdown illustrates the power of the divide-and-conquer approach inherent in Merge Sort.\n\n---\n```java []\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        mergeSort(nums,0,nums.length);\n        return nums;\n    }\n\n    static void mergeSort(int[] arr,int s,int e){\n        if(e-s==1){\n            return;\n        }\n\n        int m=s+(e-s)/2;\n\n        mergeSort(arr,s,m);\n        mergeSort(arr,m,e);\n\n         merge(arr,s,m,e);\n    }\n\n    static void merge(int[] arr,int s,int m,int e){\n        int i=s,j=m,k=0;\n        int [] mix=new int[e-s];\n\n        while(i<m && j<e){\n            if(arr[i]<arr[j]){\n                mix[k++]=arr[i++];\n            }else{\n                mix[k++]=arr[j++];\n            }\n        }\n\n        while(i<m){\n            mix[k++]=arr[i++];\n        }\n        while(j<e){\n            mix[k++]=arr[j++];\n        }\n\n        //System.arraycopy(mix,0,arr,0,mix.length);\n        for (int l = 0; l < mix.length; l++) {\n      arr[s + l] = mix[l];\n    }\n    }\n}\n\n```\n```python3 []\nclass Solution:\n    def sortArray(self, nums):\n        self.mergeSort(nums, 0, len(nums))\n        return nums\n\n    def mergeSort(self, arr, s, e):\n        if e - s <= 1:\n            return\n\n        m = s + (e - s) // 2\n\n        self.mergeSort(arr, s, m)\n        self.mergeSort(arr, m, e)\n\n        self.merge(arr, s, m, e)\n\n    def merge(self, arr, s, m, e):\n        i, j, k = s, m, 0\n        mix = [0] * (e - s)\n\n        while i < m and j < e:\n            if arr[i] < arr[j]:\n                mix[k] = arr[i]\n                i += 1\n            else:\n                mix[k] = arr[j]\n                j += 1\n            k += 1\n\n        while i < m:\n            mix[k] = arr[i]\n            i += 1\n            k += 1\n        while j < e:\n            mix[k] = arr[j]\n            j += 1\n            k += 1\n\n        for l in range(len(mix)):\n            arr[s + l] = mix[l]\n```\n```C++ []\nclass Solution {\npublic:\n    vector<int> sortArray(vector<int>& nums) {\n        mergeSort(nums, 0, nums.size());\n        return nums;\n    }\n\nprivate:\n    void mergeSort(vector<int>& arr, int s, int e) {\n        if (e - s <= 1) {\n            return;\n        }\n\n        int m = s + (e - s) / 2;\n\n        mergeSort(arr, s, m);\n        mergeSort(arr, m, e);\n\n        merge(arr, s, m, e);\n    }\n\n    void merge(vector<int>& arr, int s, int m, int e) {\n        int i = s, j = m, k = 0;\n        vector<int> mix(e - s);\n\n        while (i < m && j < e) {\n            if (arr[i] < arr[j]) {\n                mix[k++] = arr[i++];\n            } else {\n                mix[k++] = arr[j++];\n            }\n        }\n\n        while (i < m) {\n            mix[k++] = arr[i++];\n        }\n        while (j < e) {\n            mix[k++] = arr[j++];\n        }\n\n        for (int l = 0; l < mix.size(); l++) {\n            arr[s + l] = mix[l];\n        }\n    }\n};\n```\n\n---\n![upvote.png](https://assets.leetcode.com/users/images/e6f4f26f-a7f5-465b-8ec1-aa665db072f9_1719537871.6475258.png)\n\n---\n
['Array', 'Divide and Conquer', 'Sorting', 'Merge Sort', 'C++', 'Java', 'Python3']