Merge Sort
\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        int N = nums.length;\n        mergeSort(nums, 0, N-1);\n        return nums;\n    }\n    \
```\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        int N = nums.length;\n        mergeSort(nums, 0, N-1);\n        return nums;\n    }\n    \n    \n    void mergeSort(int[] nums, int start, int end){\n        if (end - start+1 <= 1) return; //Already sorted.\n        int mi = start + (end - start)/ 2;\n        mergeSort(nums, start, mi);\n        mergeSort(nums, mi+1, end);\n        merge(nums, start,mi, end);\n    }\n    \n    void merge(int[] nums, int start, int mi, int end){\n        int lp = start;\n        int rp = mi + 1;\n        int[] buffer = new int[end-start+1];\n        int t = 0; //buffer pointer\n        \n        while (lp <= mi && rp <= end){\n            if (nums[lp] < nums[rp]){\n                buffer[t++] = nums[lp++];\n            }else{\n                buffer[t++] = nums[rp++];\n            }\n        }\n        \n        while (lp <= mi) buffer[t++] = nums[lp++];\n        while (rp <= end) buffer[t++] = nums[rp++];\n        //Now copy sorted buffer into original array\n        for (int i = start; i <= end; i++){\n            nums[i] = buffer[i-start];\n        }\n    }\n    \n    \n}\n```
[]