MergeSort Explained in detail with DIAGRAM 🔥| C++✔️ | Java✔️ | Python✔️
Intuition\n Describe your first thoughts on how to solve this problem. \n-  Merge sort is a divide-and-conquer algorithm that splits the array into halves, recu
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n-  Merge sort is a divide-and-conquer algorithm that splits the array into halves, recursively sorts each half, and then merges the sorted halves back together. Here\'s a detailed explanation of the code, along with the intuition, approach, and a diagram of the algorithm flow.\n1. Divide: Split the array into two halves.\n2. Conquer: Recursively sort each half.\n3. Combine: Merge the two sorted halves to produce a single sorted array.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. merge Function:\n\n- Parameters: A (original array), start, mid, end (indices), and buff (temporary buffer).\n- Initialization: left points to the start of the left half, right points to the start of the right half, and s is the size of the subarray.\n- Merge Process:\nCompare elements from the left and right subarrays and place the smaller one into the buffer.\nIf one subarray is exhausted, copy the remaining elements from the other subarray.\n- Copy Back: Copy the merged elements from the buffer back to the original array.\n\n![image.png](https://assets.leetcode.com/users/images/4cf899b0-e298-4480-b0aa-aebaae9687cd_1721871159.897592.png)\n\n2. mergeSort Function:\n\n- Base Case: If the subarray has one or zero elements, it is already sorted.\n- Recursive Case: Split the array into two halves, sort each half, and merge them.\n- Mid Calculation: mid = start + (end - start) / 2 to avoid overflow.\nsortArray Function:\n\n- Initializes the buffer and calls mergeSort on the entire array.\n- Returns the sorted array.\n\n\n![image.png](https://assets.leetcode.com/users/images/558d79d7-8bec-4e6c-8218-fabf52a9a2cb_1721871196.116041.png)\n\n\n\n# Complexity\n1. Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- Divide Phase:\nEach recursive call splits the array into two halves. This gives a logarithmic number of levels: O(logn)\n- Conquer Phase:\nAt each level of recursion, the merge function processes the entire array. This involves comparing and copying elements, which takes linear time: O(n).\n\n2. Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n- O(n)\n\n\n\n```C++ []\nclass Solution {\npublic:\n    void merge(vector<int>& A, int start, int mid, int end, vector<int>& buff)\n    {\n        int left=start, right=mid+1;\n        int s=end-start+1;\n        for(int i=0; i<s; i++)\n        {       \n            int i0=start+i;\n            if(left>mid){\n                buff[i0]=A[right];\n                right++;\n            } else if (right>end){\n                buff[i0]=A[left];\n                left++;\n            } else  if (A[left]<A[right]){\n                buff[i0]=A[left];\n                left++;\n            } else{\n                buff[i0]=A[right];\n                right++;\n            }\n        }\n        for(int i=start; i<start+s; i++) A[i]=buff[i];\n    }\n    void mergeSort(vector<int>& A, int start, int end, vector<int>& buff )\n    {\n        if(end<=start) return;\n        int mid=start+(end-start)/2;\n        mergeSort(A, start, mid, buff);\n        mergeSort(A, mid+1, end, buff);\n        merge(A, start, mid, end, buff);\n    }\n    vector<int> sortArray(vector<int>& nums) {\n        vector<int> buff(nums.size());\n        mergeSort(nums, 0, nums.size()-1 ,buff);\n        return nums;\n    }\n};\n```\n```Java []\nclass Solution {\n    public void merge(int[] A, int start, int mid, int end, int[] buff) {\n        int left = start, right = mid + 1;\n        int s = end - start + 1;\n        \n        for (int i = 0; i < s; i++) {\n            int i0 = start + i;\n            if (left > mid) {\n                buff[i0] = A[right];\n                right++;\n            } else if (right > end) {\n                buff[i0] = A[left];\n                left++;\n            } else if (A[left] < A[right]) {\n                buff[i0] = A[left];\n                left++;\n            } else {\n                buff[i0] = A[right];\n                right++;\n            }\n        }\n        \n        for (int i = start; i < start + s; i++) {\n            A[i] = buff[i];\n        }\n    }\n\n    public void mergeSort(int[] A, int start, int end, int[] buff) {\n        if (end <= start) {\n            return;\n        }\n        \n        int mid = start + (end - start) / 2;\n        mergeSort(A, start, mid, buff);\n        mergeSort(A, mid + 1, end, buff);\n        merge(A, start, mid, end, buff);\n    }\n\n    public int[] sortArray(int[] nums) {\n        int[] buff = new int[nums.length];\n        mergeSort(nums, 0, nums.length - 1, buff);\n        return nums;\n    }\n\n    public static void main(String[] args) {\n        Solution solution = new Solution();\n        int[] nums = {38, 27, 43, 3, 9, 82, 10};\n        int[] sortedNums = solution.sortArray(nums);\n        System.out.println(Arrays.toString(sortedNums));\n    }\n}\n\n```\n```python []\nclass Solution(object):\n    def merge(self, A, start, mid, end, buff):\n        left, right = start, mid + 1\n        s = end - start + 1\n\n        for i in range(s):\n            i0 = start + i\n            if left > mid:\n                buff[i0] = A[right]\n                right += 1\n            elif right > end:\n                buff[i0] = A[left]\n                left += 1\n            elif A[left] < A[right]:\n                buff[i0] = A[left]\n                left += 1\n            else:\n                buff[i0] = A[right]\n                right += 1\n\n        for i in range(start, start + s):\n            A[i] = buff[i]\n\n    def mergeSort(self, A, start, end, buff):\n        if end <= start:\n            return\n\n        mid = start + (end - start) // 2\n        self.mergeSort(A, start, mid, buff)\n        self.mergeSort(A, mid + 1, end, buff)\n        self.merge(A, start, mid, end, buff)\n\n    def sortArray(self, nums):\n        """\n        :type nums: List[int]\n        :rtype: List[int]\n        """\n        buff = [0] * len(nums)\n        self.mergeSort(nums, 0, len(nums) - 1, buff)\n        return nums\n\n\n\n```\n\n
['Array', 'Divide and Conquer', 'Merge Sort', 'Python', 'C++', 'Java']