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 }