import java.io.BufferedInputStream; import java.util.Scanner; public class MergeSort { static int[] temp; private static void mergeSort(int[] arr, int l, int r){ if( l >= r){ return; } int mid = (l + r) / 2; //归并排序就是先进行两部分的递归 mergeSort(arr, l ,mid);mergeSort(arr, mid+1, r); int k = 0;//排序后的数组累积的元素个数 int i = l; int j = mid + 1;//制作的指针 while(i <= mid && j <= r){ if(arr[i] <= arr[j]) { temp[k++] = arr[j++]; }else{ temp[k++] = arr[i++]; } while (i <= mid) temp[k++] = arr[i++];//如果前半部分的数组有剩余，则将数组中的元素移动到temp数组中 while (j <= r) temp[k++] = arr[j++]; for(i = l, k = 0; i <= r; i++, k++){//将temp中的数组复制到arr数组中 arr[i] = temp[k]; } } } public static void main(String[] args) { Scanner in = new Scanner(new BufferedInputStream(System.in)); int n = in.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; i++){ arr[i] = in.nextInt(); } mergeSort(arr,0, n-1); for(int i = 0; i < n; i++){ System.out.print(arr[i] + " "); } } }

&& j <= r){//比较两部分的元素，并归并 if(arr[i] <= arr[j]){ temp[k++] = arr[i++]; } else{ temp[k++] = arr[j++]; } } while(i <= mid){//若左边还有剩余元素，则直接放到temp数组中 temp[k++] = arr[i++]; } while(j <= r){//若右边还有剩余元素，则直接放到temp数组中 temp[k++] = arr[j++]; } //将排序后的temp数组复制回原数组arr中 for(int p = 0; p < k; p++){ arr[l + p] = temp[p]; } } public static void main(String[] args) { Scanner in = new Scanner(new BufferedInputStream(System.in)); int n = in.nextInt(); int[] arr = new int[n]; temp = new int[n]; for(int i = 0; i < n; i++){ arr[i] = in.nextInt(); } mergeSort(arr, 0, n - 1); for(int i = 0; i < n; i++){ System.out.print(arr[i] + " "); } } }