✅ Java | Merge Sort | Easy
Merge Sort Time Complexity -> Best :- O(N log N)\tAverage :- O(N log N)\tWorst :- O(N log N)\t\nSpace Complexity :- O(N)\nStable and not in-place\nExplanation :
**Merge Sort Time Complexity -> Best :- O(N log N)\tAverage :- O(N log N)\tWorst :- O(N log N)\t\nSpace Complexity :- O(N)\nStable and not in-place\nExplanation :- [Link](https://youtu.be/ogjf7ORKfd8)**\n```\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        mergeSort(nums,0,nums.length-1);\n        return nums;\n    }\n    public static void mergeFun(int[] arr, int l, int m, int r) {\n        int n1 = m + 1 - l;\n        int n2 = r - m;\n        int[] left = new int[n1];\n        for (int i = 0; i < n1; i++) {\n            left[i] = arr[l + i];\n        }\n        int[] right = new int[n2];\n        for (int i = 0; i < n2; i++) {\n            right[i] = arr[m + 1 + i];\n        }\n        int i = 0, j = 0, k = l;\n        while (i < n1 || j < n2) {\n            if (j == n2 || i < n1 && left[i] < right[j])\n                arr[k++] = left[i++];\n            else\n                arr[k++] = right[j++];\n        }\n    }\n\n    public static void mergeSort(int[] arr, int low, int high) {\n        if (low < high) {\n            int middle = (high - low) / 2 + low;\n            mergeSort(arr, low, middle);\n            mergeSort(arr, middle + 1, high);\n            mergeFun(arr, low, middle, high);\n        }\n    }\n}\n```\n![image](https://assets.leetcode.com/users/images/c663feb7-65b9-4d58-9ce4-1168250b9e99_1677630567.3774197.jpeg)\n
['Sorting', 'Merge Sort', 'Java']