✅ Easy 3 step Sort Cpp / Java / Py / JS Solution | MergeSort _DivideNdConquer🏆|
You may be wondering why we don\'t use Bubble Sort, Insertion Sort, or Selection Sort for this problem?\nThe constraint specifies that the solution must achieve
####  You may be wondering why we don\'t use Bubble Sort, Insertion Sort, or Selection Sort for this problem?\nThe constraint specifies that the solution must achieve a time complexity of O(n log n).. or better. Algorithms like Bubble Sort, Insertion Sort, and Selection Sort have a time complexity of O(n^2), which is inefficient for large datasets. Therefore, using these algorithms would result in exceeding the time limits. Instead, algorithms like Quick Sort or Merge Sort, which have a time complexity of \uD835\uDC42 (\uD835\uDC5B log \uD835\uDC5B), are more suitable for meeting the constraints and ensuring efficient performance\n## Visualization\n\n Merge Sort Visualization -Consider nums = [5, 1, 1, 2, 0, 0]\n```\n// Initial input:\nnums = [5, 1, 1, 2, 0, 0]\n\n// Divide step:\n\n// First split:\nLeft half: [5, 1, 1]\nRight half: [2, 0, 0]\n\n// Second split (Left half):\nLeft half: [5]\nRight half: [1, 1]\n\n// Second split (Right half):\nLeft half: [2]\nRight half: [0, 0]\n\n// Third split (Left half of right half):\nLeft half: [1]\nRight half: [1]\n\n// Third split (Right half of right half):\nLeft half: [0]\nRight half: [0]\n\n// Conquer step:\n\n// First merge (Right half of right half):\nMerging: [0] and [0] => [0, 0]\n\n// First merge (Left half of right half):\nMerging: [1] and [1] => [1, 1]\n\n// Second merge (Right half):\nMerging: [2] and [0, 0] => [0, 0, 2]\n\n// Second merge (Left half):\nMerging: [5] and [1, 1] => [1, 1, 5]\n\n// Final merge:\nMerging: [1, 1, 5] and [0, 0, 2] => [0, 0, 1, 1, 2, 5]\n\n// Final output:\nnums = [0, 0, 1, 1, 2, 5]\n\n```\n### C++\n```\n//Easy to understand\nclass Solution\n{\npublic:\n    vector<int> sortArray(vector<int> &nums)\n    {\n        mergeSort(nums, 0, nums.size() - 1);\n        return nums;\n    }\n\nprivate:\n    void merge(vector<int> &nums, int low, int mid, int high)\n    {\n        vector<int> temp;\n        int left = low;\n        int right = mid + 1;\n        // while\n        while (left <= mid && right <= high)\n        {\n            if (nums[left] <= nums[right])\n            {\n                temp.push_back(nums[left]);\n                left++;\n            }\n            else\n            {\n                temp.push_back(nums[right]);\n                right++;\n            }\n        }\n        // push remaining\n        while (left <= mid)\n        {\n            temp.push_back(nums[left]);\n            left++;\n        }\n        while (right <= high)\n        {\n\n            temp.push_back(nums[right]);\n            right++;\n        }\n        // modify in place\n        for (int i = low; i <= high; i++)\n        {\n            nums[i] = temp[i - low];\n        }\n    }\n\n    void mergeSort(vector<int> &nums, int low, int high)\n    {\n        if (low == high)\n        {\n            return;\n        }\n        int mid = (low + high) / 2;\n        mergeSort(nums, low, mid);\n        mergeSort(nums, mid + 1, high);\n\n        merge(nums, low, mid, high);\n    }\n};\n\n```\n```\n//Optimized\nclass Solution {\npublic:\n    vector<int> sortArray(vector<int>& nums) {\n        mergeSort(nums, 0, nums.size() - 1);\n        return nums;\n    }\n\nprivate:\n    void mergeSort(vector<int>& nums, int left, int right) {\n        // Base case: if the subarray has one or zero elements, it is already sorted\n        if (left >= right) return;\n        \n        // Divide: find the midpoint to split the array into two halves\n        int mid = left + (right - left) / 2;\n        \n        // Conquer: recursively sort the left and right halves\n        mergeSort(nums, left, mid);\n        mergeSort(nums, mid + 1, right);\n        \n        // Combine: merge the sorted halves\n        merge(nums, left, mid, right);\n    }\n\n    void merge(vector<int>& nums, int left, int mid, int right) {\n        int n1 = mid - left + 1;\n        int n2 = right - mid;\n        \n        // Create temporary arrays to hold the left and right halves\n        vector<int> leftArray(n1);\n        vector<int> rightArray(n2);\n        \n        // Copy data to temporary arrays\n        for (int i = 0; i < n1; ++i)\n            leftArray[i] = nums[left + i];\n        for (int i = 0; i < n2; ++i)\n            rightArray[i] = nums[mid + 1 + i];\n        \n        // Initial indices for left, right, and merged subarrays\n        int i = 0, j = 0, k = left;\n        \n        // Merge the temporary arrays back into the original array\n        while (i < n1 && j < n2) {\n            if (leftArray[i] <= rightArray[j]) {\n                nums[k++] = leftArray[i++];\n            } else {\n                nums[k++] = rightArray[j++];\n            }\n        }\n        \n        // Copy any remaining elements of leftArray\n        while (i < n1) {\n            nums[k++] = leftArray[i++];\n        }\n        \n        // Copy any remaining elements of rightArray\n        while (j < n2) {\n            nums[k++] = rightArray[j++];\n        }\n    }\n};\n\n\n```\n### Java\n```\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        mergeSort(nums, 0, nums.length - 1);\n        return nums;\n    }\n\n    private void mergeSort(int[] nums, int left, int right) {\n        if (left >= right) return;\n\n        int mid = left + (right - left) / 2;\n\n        mergeSort(nums, left, mid);\n        mergeSort(nums, mid + 1, right);\n\n        merge(nums, left, mid, right);\n    }\n\n    private void merge(int[] nums, int left, int mid, int right) {\n        int n1 = mid - left + 1;\n        int n2 = right - mid;\n\n        int[] leftArray = new int[n1];\n        int[] rightArray = new int[n2];\n\n        for (int i = 0; i < n1; ++i)\n            leftArray[i] = nums[left + i];\n        for (int i = 0; i < n2; ++i)\n            rightArray[i] = nums[mid + 1 + i];\n\n        int i = 0, j = 0, k = left;\n\n        while (i < n1 && j < n2) {\n            if (leftArray[i] <= rightArray[j]) {\n                nums[k++] = leftArray[i++];\n            } else {\n                nums[k++] = rightArray[j++];\n            }\n        }\n\n        while (i < n1) {\n            nums[k++] = leftArray[i++];\n        }\n\n        while (j < n2) {\n            nums[k++] = rightArray[j++];\n        }\n    }\n}\n\n\n```\n\n### Python3\n```\n\nclass Solution:\n    def sortArray(self, nums: List[int]) -> List[int]:\n        self.mergeSort(nums, 0, len(nums) - 1)\n        return nums\n\n    def mergeSort(self, nums: List[int], left: int, right: int) -> None:\n        if left >= right:\n            return\n\n        mid = (left + right) // 2\n\n        self.mergeSort(nums, left, mid)\n        self.mergeSort(nums, mid + 1, right)\n\n        self.merge(nums, left, mid, right)\n\n    def merge(self, nums: List[int], left: int, mid: int, right: int) -> None:\n        n1 = mid - left + 1\n        n2 = right - mid\n\n        leftArray = nums[left:mid + 1]\n        rightArray = nums[mid + 1:right + 1]\n\n        i = j = 0\n        k = left\n\n        while i < n1 and j < n2:\n            if leftArray[i] <= rightArray[j]:\n                nums[k] = leftArray[i]\n                i += 1\n            else:\n                nums[k] = rightArray[j]\n                j += 1\n            k += 1\n\n        while i < n1:\n            nums[k] = leftArray[i]\n            i += 1\n            k += 1\n\n        while j < n2:\n            nums[k] = rightArray[j]\n            j += 1\n            k += 1\n```\n### JavaScript\n```\n/**\n * @param {number[]} nums\n * @return {number[]}\n */\nvar sortArray = function(nums) {\n    mergeSort(nums, 0, nums.length - 1);\n    return nums;\n};\n\nfunction mergeSort(nums, left, right) {\n    if (left >= right) return;\n\n    const mid = Math.floor((left + right) / 2);\n\n    mergeSort(nums, left, mid);\n    mergeSort(nums, mid + 1, right);\n\n    merge(nums, left, mid, right);\n}\n\nfunction merge(nums, left, mid, right) {\n    const n1 = mid - left + 1;\n    const n2 = right - mid;\n\n    const leftArray = new Array(n1);\n    const rightArray = new Array(n2);\n\n    for (let i = 0; i < n1; ++i)\n        leftArray[i] = nums[left + i];\n    for (let i = 0; i < n2; ++i)\n        rightArray[i] = nums[mid + 1 + i];\n\n    let i = 0, j = 0, k = left;\n\n    while (i < n1 && j < n2) {\n        if (leftArray[i] <= rightArray[j]) {\n            nums[k++] = leftArray[i++];\n        } else {\n            nums[k++] = rightArray[j++];\n        }\n    }\n\n    while (i < n1) {\n        nums[k++] = leftArray[i++];\n    }\n\n    while (j < n2) {\n        nums[k++] = rightArray[j++];\n    }\n}\n\n\n\n```\n#### STAY COOL STAY DISCIPLINED..\n\n![image](https://assets.leetcode.com/users/images/ad294515-01e3-4704-a668-9bcc5b0e822c_1717851160.1975598.gif)
['Array', 'Divide and Conquer', 'C', 'Sorting', 'Heap (Priority Queue)', 'Python', 'Java', 'Python3', 'JavaScript']