归并排序-Merge Sort

归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

实现步骤
1,将序列进行归并操作。直至每分组只有一个数字。将分组内每相邻两个数字进行归并操作，形成n个序列，对每个序列两两合并进行排序，形成n/2个序列，每个序列内都是有序的。
2,将上述序列再次归并，形成n/4个序列，每个序列包含四个元素。
3,再次进行分组，分组数量处以2，对分组内元素进行排序。
4,重复以上步骤，直到所有元素排序完毕。

实现代码：

public void solution() {
    int[] befArrays = {3, 5, 1, 4, 12, 18, 19, 20, 9, 3, 15, 7, 0};
    int length = befArrays.length;

    this.mergeSort(befArrays, 0, length-1);

    for (int i=0; i<length; i++) {
        System.out.printf(befArrays[i] + "\t");
    }
}

public void mergeSort(int[] befArrays, int left, int right) {
    if (left >= right) {
        return;
    }

    int middle = (left+right)/2;
    this.mergeSort(befArrays, left, middle);
    this.mergeSort(befArrays, middle+1, right);

    int[] newArrays = new int[right-left+1];
    int index=0;
    int lIndex=left;
    int rIndex=middle+1;
    while (lIndex<=middle&&rIndex<=right) {
        if (befArrays[lIndex]<befArrays[rIndex]) {
            newArrays[index++] = befArrays[lIndex++];
        } else {
            newArrays[index++] = befArrays[rIndex++];
        }
    }

    while (lIndex<=middle) {
        newArrays[index++] = befArrays[lIndex++];
    }
    while (rIndex<=right) {
        newArrays[index++] = befArrays[rIndex++];
    }

    index = 0;
    while (index < newArrays.length) {
        befArrays[left+index] = newArrays[index];
        index++;
    }
}

算法分析：