归并排序

什么是归并排序呢，归并排序就是先分再合，所谓先分再合就是先分到不能再分，也就是每组一个元素，再原来的两组合并成一组，在合并途中，进行比较来排序，形成有序数组，以此类推就可以得出最后一个有序的数组。

---

如何合并：

用l（left）表示左数组的第一个元素，

m（middle）表示左数组的最后一个元素，

r（right）代表右数组最后一个元素，

m+1代表右数组第一个元素。

k表示新数组的最后一个元素后面一个位置。

左数组的第一个元素和右数组进行比较，最小的放在第k个位置上，k++，如果左数组小则i++，右数组小则j++，直到一方比完，另一方的所有剩余元素赋值到k的位置。

---

先创建一个与原数组等大的数组，将数组进行深拷贝得到两个相同的数组。

递归调用两个函数，一个分函数，一个合并函数。

package bobo.algo;

import java.util.*;

public class MergeSort{

// 我们的算法类不允许产生任何实例

    private MergeSort(){}

// 将arr[l...mid]和arr[mid+1...r]两部分进行归并

    private static void merge(Comparable[] arr, int l, int mid, int r) {

Comparable[] aux = Arrays.copyOfRange(arr, l, r+1);

        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1

        int i = l, j = mid+1;

        for(int k = l; k <= r; k ++ ){

if( i > mid ){// 如果左半部分元素已经全部处理完毕

                arr[k] = aux[j-l]; j ++;

            }

else if( j > r ){// 如果右半部分元素已经全部处理完毕

                arr[k] = aux[i-l]; i ++;

            }

else if( aux[i-l].compareTo(aux[j-l]) <0 ){// 左半部分所指元素 < 右半部分所指元素

                arr[k] = aux[i-l]; i ++;

            }

else{// 左半部分所指元素 >= 右半部分所指元素

                arr[k] = aux[j-l]; j ++;

            }

}

}

// 递归使用归并排序,对arr[l...r]的范围进行排序

    private static void sort(Comparable[] arr, int l, int r) {

if (l >= r)

return;

        int mid = (l+r)/2;

        sort(arr, l, mid);

        sort(arr, mid +1, r);

if(array[i]>array[i+1])

        merge(arr, l, mid, r);

    }

public static void sort(Comparable[] arr){

int n = arr.length;

        sort(arr, 0, n-1);

    }

---

插入排序在数量较小时比归并排序快

所以当少于15个数时可以用插入法，大于15可以用归并算法