publicclassMergeSort{ publicstaticint[] sort(int[] nums){ if(nums==null || nums.length==0) returnnull; int len = nums.length; int[] A = newint[len]; System.arraycopy(nums, 0, A, 0, len); mergeSort(A, 0, A.length-1); return A; } privatestaticvoidmergeSort(int[] nums, int i, int j){ if(i>=j) return; int m = i + (j-i)/2; mergeSort(nums,i, m); mergeSort(nums, m+1, j); // m位置属于左数组 merge(nums, i, m, j); }
privatestaticvoidmerge(int[] nums, int i, int m, int j){ int[] leftArr = newint[m-i+1]; int[] rightArr = newint[j-m]; // 辅助数组填充 for(int l=i; l<=m; l++){ leftArr[l-i] = nums[l]; } for(int r=m+1; r<=j; r++){ rightArr[r-m-1] = nums[r]; }