归并排序（Merge Sort）

• 1945年由约翰·冯·诺伊曼（John von Neumann）首次提出
• 执行流程
  ①、不断地将当前序列平均分割成2个子序列
  ✓ 直到不能再分割（序列中只剩1个元素）
  ②、不断地将2个子序列合并成一个有序序列
  ✓ 直到最终只剩下1个有序序列

（1）归并排序 — divide实现

protected void sort() {
    leftArray = new int[array.length >> 1];
    System.out.println("排序前："+Arrays.toString(array));
    mergesort(0, array.length);
    System.out.println("排序后："+Arrays.toString(array));
}

/**
 * 对[begin,end)范围的数据进行归并排序
 */
private void mergesort(int begin, int end) {
    if (end - begin < 2) return;

    int mid = (begin + end) >> 1;
    mergesort(begin, mid);//对mid左边的元素进行分割
    mergesort(mid, end);//对mid右边的元素进行分割
    merge(begin, mid, end);
}

（2）归并排序 — merge

（3）归并排序 – merge细节

• 需要 merge 的 2 组序列存在于同一个数组中，并且是挨在一起的
  

• 为了更好地完成 merge 操作，最好将其中 1 组序列备份出来，比如 [begin, mid)
  

• li == 0，le == mid – begin

• ri == mid，re == end
  

①、归并排序 – merge — 左边先结束

• 归并排序 （merge），左边先结束，那么右边就不用动了（因为右边的剩下有序元素本来就在右边）
  

②、归并排序 – merge — 右边先结束

• 归并排序 （merge），右边先结束，那么只需要将左边的剩下的元素不断地移动到右边就行
  

（4）归并排序 – merge实现

/**
 * 将[begin,mid)和[mid,end)范围的序列合并成一个有序的序列
 */
private void merge(int begin, int mid, int end) {
    int li = 0, le = mid - begin;//左边数组(基于leftArray)
    int ri = mid, re = end;//右边数组(基于array)
    int ai = begin;//array地索引

    //备份左边数据到leftArray
    for (int i = li; i < le; i++) {
        leftArray[i] = array[begin + i];
    }

    //如果左边还没有结束
    while (li < le) {
        if (ri < re && (array[ri]-leftArray[li]) < 0) {
            array[ai++] = array[ri++];//拷贝右边数组到array
        } else {
            array[ai++] = leftArray[li++];//拷贝左边数组到array
        }
    }
}

（5）归并排序 – 复杂度分析

• 归并排序花费的时间
  ①、T (n) = 2 ∗ T (n/2) + O(n)
  ②、T (1) = O(1)
  ③、T (n) /n = T n/2 /(n/2) + O(1)
• 令 S (n) = T (n) /n
  ①、S (1) = O(1)
  ②、S(n)= S(n/2)+ O(1) = S(n/4)+ O(2) = S(n/8) + O(3) = S(n/2^k) + O(k) = S (1) + O(logn) = O(logn)
  ③、T (n) = n ∗ S (n) = O(nlogn)
• 由于归并排序总是平均分割子序列，所以最好、最坏、平均时间复杂度都是 O(nlogn) ，属于稳定排序
• 从代码中不难看出：归并排序的空间复杂度是 O (n/2 + logn) = O(n)
  n/2 用于临时存放左侧数组，logn 是因为递归调用
  

（5）归并排序 – 代码实现

import org.junit.Test;
import java.util.Arrays;

public class TestDemo {
    @Test
    public void test(){
        MergeSort mergeSort = new MergeSort();
        mergeSort.sort();
    }

    static class MergeSort {
        private int[] leftArray;
        int[] array = {15, 10, 7, 12, 16, 5, 17, 12, 9, 18};

        protected void sort() {
            leftArray = new int[array.length >> 1];
            System.out.println("排序前："+Arrays.toString(array));
            mergesort(0, array.length);
            System.out.println("排序后："+Arrays.toString(array));
        }

        /**
         * 对[begin,end)范围的数据进行归并排序
         */
        private void mergesort(int begin, int end) {
            if (end - begin < 2) return;

            int mid = (begin + end) >> 1;
            mergesort(begin, mid);//对mid左边的元素进行分割
            mergesort(mid, end);//对mid右边的元素进行分割
            merge(begin, mid, end);
        }

        /**
         * 将[begin,mid)和[mid,end)范围的序列合并成一个有序的序列
         */
        private void merge(int begin, int mid, int end) {
            int li = 0, le = mid - begin;//左边数组(基于leftArray)
            int ri = mid, re = end;//右边数组(基于array)
            int ai = begin;//array地索引

            //备份左边数据到leftArray
            for (int i = li; i < le; i++) {
                leftArray[i] = array[begin + i];
            }

            //如果左边还没有结束
            while (li < le) {
                if (ri < re && (array[ri]-leftArray[li]) < 0) {
                    array[ai++] = array[ri++];//拷贝右边数组到array
                } else {
                    array[ai++] = leftArray[li++];//拷贝左边数组到array
                }
            }
        }
    }
}
运行结果：
排序前：[15, 10, 7, 12, 16, 5, 17, 12, 9, 18]
排序后：[5, 7, 9, 10, 12, 12, 15, 16, 17, 18]