// 归并排序算法, a是数组，n表示数组大小 public static void mergeSort(int[] a, int n) { mergeSortInternally(a, 0, n-1); } // 递归调用函数 private static void mergeSortInternally(int[] a, int p, int r) { // 递归终止条件 if (p >= r) return; // 取p到r之间的中间位置q int q = (p+r)/2; // 分治递归 mergeSortInternally(a, p, q); mergeSortInternally(a, q+1, r); // 将A[p...q]和A[q+1...r]合并为A[p...r] merge(a, p, q, r); } private static void merge(int[] a, int p, int q, int r) { int i = p; int j = q+1; int k = 0; // 初始化变量i, j, k int[] tmp = new int[r-p+1]; // 申请一个大小跟a[p...r]一样的临时数组 // 1 排序 while (i<=q && j<=r) { if (a[i] <= a[j]) { tmp[k++] = a[i++]; // i++等于i:=i+1 } else { tmp[k++] = a[j++]; } } // 2 判断哪个子数组中有剩余的数据 int start = i; int end = q; if (j <= r) { start = j; end = r; } // 3 将剩余的数据拷贝到临时数组tmp while (start <= end) { tmp[k++] = a[start++]; } // 4 将tmp中的数组拷贝回a[p...r] for (i = 0; i <= r-p; ++i) { a[p+i] = tmp[i]; } }

这段代码是一个归并排序算法的实现。归并排序是一种分治算法，通过将待排序的数组不断地划分成更小的子数组，然后合并这些子数组来实现排序。

该代码中的`mergeSort`函数是对外的调用接口，它接受一个整型数组`a`和数组大小`n`作为参数，然后调用`mergeSortInternally`函数来进行递归排序。

`mergeSortInternally`函数是递归调用的实现部分，它接受一个整型数组`a`，起始位置`p`和结束位置`r`作为参数。在函数内部，首先判断递归终止条件，即当起始位置大于等于结束位置时，直接返回。然后找到起始位置和结束位置之间的中间位置`q`，然后分别递归调用`mergeSortInternally`函数对左右两个子数组进行排序。最后调用`merge`函数将排好序的子数组进行合并。

`merge`函数用于将两个已排好序的子数组合并为一个有序的数组。它接受一个整型数组`a`，起始位置`p`，中间位置`q`和结束位置`r`作为参数。在函数内部，首先创建一个临时数组`tmp`，它的大小与要合并的子数组大小相同。然后通过比较两个子数组中的元素大小，将较小的元素依次放入临时数组中。接着判断哪个子数组中还有剩余的元素，将剩余的元素拷贝到临时数组中。最后将临时数组中的元素拷贝回原数组`a`的相应位置，完成合并操作。

通过不断递归调用`mergeSortInternally`函数和合并操作，最终实现了对整个数组的排序。归并排序的时间复杂度为O(nlogn)。