java归并排序

 1 public class Solution {
 2     public static void main(String[] args) {
 3 
 4     }
 5 
 6     public static void mergeSort(int[] nums) {
 7         int[] tmp = new int[nums.length];
 8 
 9         mergeSort(nums, tmp, 0, nums.length-1);
10     }
11 
12     private static void mergeSort(int[] nums, int[] tmp, int left, int right) {
13         if(left < right) {
14             int mid = (left + right) >> 1;
15             mergeSort(nums, tmp, left, mid);
16             mergeSort(nums, tmp, mid+1, right);
17             merge(nums, tmp, left, mid+1, right);
18         }
19     }
20 
21     private static void merge(int[] nums, int[] tmp, int leftPos, int rightPos, int rightEnd) {
22         int leftEnd = rightPos-1;
23         int tmpPos = leftPos;
24         int numElements = rightEnd-leftPos+1;
25 
26         while(leftPos <= leftEnd && rightPos <= rightEnd) {
27             if(nums[leftPos] <= nums[rightPos]) {
28                 tmp[tmpPos++] = nums[leftPos++];
29             } else {
30                 tmp[tmpPos++] = nums[rightPos++];
31             }
32         }
33 
34         while(leftPos <= leftEnd) {
35             tmp[tmpPos++] = nums[leftPos++];
36         }
37 
38         while(rightPos <= rightEnd) {
39             tmp[tmpPos++] = nums[rightPos++];
40         }
41 
42         for(int i = 0; i < numElements; i++, rightEnd--) {
43             nums[rightEnd] = tmp[rightEnd];
44         }
45     }
46 }