归并排序的原理

归并排序（Merge Sort）是一种基于分治法的排序算法。其基本思想是将待排序的序列分成若干个子序列，分别对每个子序列进行排序，然后通过合并操作将这些子序列合并为一个有序的序列。归并排序采用的是递归的方式，利用两个指针分别指向两个子序列的起始位置以及一个辅助数组，先对左右子序列进行递归排序，然后再将两个有序的子序列进行合并得到最终的有序序列。

归并排序的步骤

归并排序的过程可以分为四个步骤：

  1. 分解：将待排序序列分解成若干个子序列，每个子序列包含一个元素。
  2. 排序：对每个子序列进行排序。
  3. 合并：合并相邻的两个有序子序列，得到新的有序子序列。
  4. 重复合并直到整个序列排序完成。

Java实现归并排序

下面是Java中实现归并排序的示例代码：

public class MergeSort {
  
  public void mergeSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
      return;
    }
    mergeSort(arr, 0, arr.length - 1);
  }
  
  private void mergeSort(int[] arr, int start, int end) {
    if (start < end) {
      int mid = (start + end) / 2;
      mergeSort(arr, start, mid);
      mergeSort(arr, mid + 1, end);
      merge(arr, start, mid, end);
    }
  }
  
  private void merge(int[] arr, int start, int mid, int end) {
    int[] temp = new int[arr.length];
    int p1 = start, p2 = mid + 1, k = start;
    while (p1 <= mid && p2 <= end) {
      if (arr[p1] <= arr[p2]) {
        temp[k++] = arr[p1++];
      } else {
        temp[k++] = arr[p2++];
      }
    }
    while (p1 <= mid) {
      temp[k++] = arr[p1++];
    }
    while (p2 <= end) {
      temp[k++] = arr[p2++];
    }
    for (int i = start; i <= end; i++) {
      arr[i] = temp[i];
    }
  }
}

在这段代码中，我们定义了一个`MergeSort`类，并提供了两个重载的`mergeSort`方法用于对整个数组或某个范围内的子数组进行归并排序。在`mergeSort`方法中，首先判断传入的数组是否为空或长度小于等于1，满足条件时直接返回。然后通过递归调用`mergeSort`方法将数组一分为二，再对左右两个子数组分别进行排序，最后调用`merge`方法将左右子数组合并为一个有序的数组。

在`merge`方法中，我们使用一个辅助数组`temp`来保存排序结果。定义两个指针`p1`和`p2`分别指向左右子数组的起始位置，同时定义一个变量`k`用于指向`temp`数组当前位置。然后通过比较两个指针指向的元素大小，选择较小者存入`temp`数组中，并将相应指针向后移动一位。最后将`temp`数组中的元素复制回原数组`arr`，完成合并操作。