[数据结构与算法]常见的排序算法：归并排序

1. 原理

• 归并排序采用分治法进行排序，每次将待排序区间分为两个等长的区间，直至待排序区间长度为 1 时，开始合并两个有序数组，直至整个数组有序。
  

2. 代码实现

public void mergeSort(int[] arr) {
        separate(arr, 0, arr.length - 1);
    }

    public void separate(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        int mid = low + (high - low) / 2;
        separate(arr, low, mid);
        separate(arr, mid + 1, high);
        merge(arr, low, mid, mid + 1, high);
    }

    public void merge(int[] arr, int begin1, int end1, int begin2, int end2) {
        int low = begin1;
        int[] tmp = new int[end2 - begin1 + 1];
        int index = 0;
        while (begin1 <= end1 && begin2 <= end2) {
            if (arr[begin1] < arr[begin2]) {
                tmp[index++] = arr[begin1++];
            } else {
                tmp[index++] = arr[begin2++];
            }
        }
        while (begin1 <= end1) {
            tmp[index++] = arr[begin1++];
        }
        while (begin2 <= end2) {
            tmp[index++] = arr[begin2++];
        }
        for (int i = 0; i < tmp.length; i++) {
            arr[i + low] = tmp[i];
        }
    }

• 排序的稳定性：两个相等的数字在排序结束后，位置没有交换，我们就认为这个排序是稳定的，同时也不存在跳跃式的交换，所以归并排序是稳定的。

3. 复杂度

• 小菜鸡一枚，大家有问题可以评论，大家一起讨论。