简单版本

两个已经排序好的数组，

1,3,5,7,8,9......
2,4,5,7,10......

显而易见，用两个指针m、n，分别指向两个数组的开头

  • 比较m、n大小
  • 小的指针所在点放入新数组，并将该指针向后移动一位
  • 重复比较，移动
  • 最后有一个指针到了尽头，将另外的指针剩余部分放入新数组尾部

这样就完成了排序。

有序？不存在的

如果只有一个数组，而且是无序的，想要使用归并排序，怎么办？

  • 按长度分成2个数组，是有序的话，就归并
  • 不是有序的，分成4个数组，是有序的话，就归并
  • 还不是有序的，一直分成有序的为止，此时每个数组长度为1
  • 然后归并

代码

static void sort(int[] array) {
    for (int i = 1; i < array.length / 2; i *= 2) {
        int step = i * 2;
        for (int j = 0; j + step <= array.length; j += step) {
            merge(array, j, i, i);
        }
        final int left = array.length % (i * 2);
        if (left > 0) {
            merge(array, array.length - step - left, step, left);
        }
    }
}
static void merge(int[] array, int index, int ll, int rl) {
    int m = index;
    int n = index + ll;
    while (m < n && n < index + ll + rl) {
        if (array[m] > array[n]) {
            move(array, n, m);//insert n before m
            n++;
        }
        m++;
    }
}
static void move(int[] array, int from, int to) {
    int temp = array[from];
    int p = to;
    while (p <= from) {
        array[from] = array[p]; //临时保存当前值
        array[p] = temp; //当前值设置为上一个temp的值
        temp = array[from]; //保存当前值
        p++;
    }
}