Given an array of integers nums, sort the array in ascending order.
Example 1:
Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Example 2:
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Constraints:
- 1 <= nums.length <= 5 * 104
- -5 * 104 <= nums[i] <= 5 * 104
class Solution {
public int[] sortArray(int[] nums) {
mergeSort(nums, 0, nums.length-1);
return nums;
}
private void mergeSort(int[] nums, int begin, int end) {
if (begin < end) {
int mid = (begin + end) / 2;
mergeSort(nums, begin, mid);
mergeSort(nums, mid + 1, end);
merge(nums, begin, mid, end);
}
}
private void merge(int[] nums, int begin, int mid, int end){
int[] temp = new int[nums.length];
int i = begin;
int j = mid + 1;
int t = 0;
while(i<=mid && j<=end){
if(nums[i]<nums[j]){
temp[t++] = nums[i++];
}else{
temp[t++] = nums[j++];
}
}
while(i<=mid){
temp[t++] = nums[i++];
}
while(j<=end){
temp[t++] = nums[j++];
}
t = 0;
while(begin<=end){
nums[begin++] = temp[t++];
}
}
}