🧐Simple way 💻 🔥Merge Sort in Java 📝, Python 🐍, and C++ 🖥️ with Video Explanation 🎥
Intuition\n Describe your first thoughts on how to solve this problem. \nMerge sort is a sorting algorithm that uses the divide and conquer approach to sort an 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nMerge sort is a sorting algorithm that uses the divide and conquer approach to sort an array or a list. In this algorithm, the given array is recursively divided into two halves until the base case of having a single element is reached. The two halves are then merged by comparing and sorting them, thus generating a sorted array\n\n# Approach\nThe merge sort algorithm follows the divide and conquer approach to sort an array. The basic steps involved in the merge sort algorithm are as follows:\n\n1. Divide the array into two halves (left and right).\n2. Recursively apply the merge sort algorithm on the left half until it is sorted.\n3. Recursively apply the merge sort algorithm on the right half until it is sorted.\n5. Merge the left and right halves to obtain a sorted array.\n6. The merging process is performed by comparing and sorting the elements in the left and right halves one by one.\n<!-- Describe your approach to solving the problem. -->\n![image.png](https://assets.leetcode.com/users/images/b7c3116f-9959-44d9-bfd6-d1d070ffa60e_1677632153.1925292.png)\n\n\n\n\n# Video reference\n\n<iframe width="560" height="315" src="https://www.youtube.com/embed/mB5HXBb_HY8" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>\n\n![image.png](https://assets.leetcode.com/users/images/2b37d2cc-3ca9-4b0c-866d-48abc59d8fa5_1677216789.1769023.png)\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution.\uD83D\uDE0A Keep Learning\n```\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity of the merge sort algorithm is $$O(nlogn)$$ in all cases. This is because the algorithm divides the array into two halves at each recursive call, and the merging process takes $$O(n)$$ time. Therefore, the overall time complexity is given by `T(n) = 2T(n/2) + O(n)`, which results in $$O(nlogn)$$ time complexity.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity of the merge sort algorithm is $$O(n)$$. This is because the algorithm creates temporary arrays to store the left and right halves of the array during the merging process. The maximum size of the temporary arrays is` n/2`, which results in $$O(n)$$ space complexity.\n\n# Code\n``` java []\npublic class Solution {\n    public int[] sortArray(int[] nums) {\n        mergeSort(nums, 0, nums.length - 1); // Call the recursive Merge Sort \n        return nums;\n    }\nprivate void mergeSort(int[] nums, int start, int end) {\n    if (start < end) { // Base case - Check if array has only 1 element\n        int mid = (start + end) / 2; // Calculate the middle index\n        mergeSort(nums, start, mid); // Recursively call Merge Sort on left subarray\n        mergeSort(nums, mid + 1, end); // Recursively call Merge Sort on right subarray\n        merge(nums, start, mid, end); // Merge the sorted left and right subarrays\n    }\n}\n\nprivate void merge(int[] nums, int start, int mid, int end) {\n    int[] temp = new int[end - start + 1]; // Create a temporary array to store the merged subarrays\n    int i = start, j = mid + 1, k = 0; // Initialize indices for left subarray, right subarray, and temporary array\n    \n    // Compare elements in the left and right subarrays, and store the smaller element in the temporary array\n    while (i <= mid && j <= end) {\n        if (nums[i] < nums[j]) {\n            temp[k++] = nums[i++];\n        } else {\n            temp[k++] = nums[j++];\n        }\n    }\n    \n    // Copy any remaining elements in the left subarray to the temporary array\n    while (i <= mid) {\n        temp[k++] = nums[i++];\n    }\n    \n    // Copy any remaining elements in the right subarray to the temporary array\n    while (j <= end) {\n        temp[k++] = nums[j++];\n    }\n    \n    // Copy the merged subarray from the temporary array back to the original array\n    for (int p = 0; p < temp.length; p++) {\n        nums[start + p] = temp[p];\n    }\n}\n}\n\n```\n```C++ []\nclass Solution {\npublic:\n    void mergeSort(vector<int>& nums, int start, int end) {\n        if (start >= end) {\n            return;\n        }\n        int mid = start + (end - start) / 2;\n        mergeSort(nums, start, mid);\n        mergeSort(nums, mid + 1, end);\n        merge(nums, start, mid, end);\n    }\n    \n    void merge(vector<int>& nums, int start, int mid, int end) {\n        vector<int> temp(end - start + 1);\n        int i = start, j = mid + 1, k = 0;\n        while (i <= mid && j <= end) {\n            if (nums[i] < nums[j]) {\n                temp[k++] = nums[i++];\n            } else {\n                temp[k++] = nums[j++];\n            }\n        }\n        while (i <= mid) {\n            temp[k++] = nums[i++];\n        }\n        while (j <= end) {\n            temp[k++] = nums[j++];\n        }\n        for (int p = 0; p < temp.size(); p++) {\n            nums[start + p] = temp[p];\n        }\n    }\n    \n    vector<int> sortArray(vector<int>& nums) {\n        mergeSort(nums, 0, nums.size() - 1);\n        return nums;\n    }\n};\n\n```\n```python []\nclass Solution:\n    def mergeSort(self, nums, start, end):\n        if start >= end:\n            return\n        mid = start + (end - start) // 2\n        self.mergeSort(nums, start, mid)\n        self.mergeSort(nums, mid + 1, end)\n        self.merge(nums, start, mid, end)\n        \n    def merge(self, nums, start, mid, end):\n        temp = []\n        i, j = start, mid + 1\n        while i <= mid and j <= end:\n            if nums[i] < nums[j]:\n                temp.append(nums[i])\n                i += 1\n            else:\n                temp.append(nums[j])\n                j += 1\n        while i <= mid:\n            temp.append(nums[i])\n            i += 1\n        while j <= end:\n            temp.append(nums[j])\n            j += 1\n        nums[start:end+1] = temp\n        \n    def sortArray(self, nums: List[int]) -> List[int]:\n        self.mergeSort(nums, 0, len(nums) - 1)\n        return nums\n\n```\n# Please Comment\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution comment below if you like it.\uD83D\uDE0A\n```\n
['Divide and Conquer', 'Merge Sort', 'Python', 'C++', 'Java']