java排序算法(六)： 归并排序

归并排序

每次把待排序列分成两部分，分别对这两部分递归地用归并排序，完成后把这两个子部分合并成一个有序序列。

package algorithms.sort;

import algorithms.AbstractSort;

public class MergeSort extends AbstractSort {

	@Override
	public void sort(int[] array, int from, int len) {
		if (len <= 1) {
			return;
		}

		int[] tmpArray = new int[array.length];
		mergeSort(array, from, len - 1, tmpArray);
	}

	private void mergeSort(int[] array, int from, int to, int[] tmpArray) {

		if (to <= from) {
			return;
		}

		int middle = (from + to) / 2;
		mergeSort(array, from, middle, tmpArray);
		mergeSort(array, middle + 1, to, tmpArray);
		merge(array, from, to, middle, tmpArray);
	}

	private void merge(int[] array, int from, int to, int middle, int[] tmpArray) {
		int k = 0;
		int leftIndex = 0;
		int rightIndex = to - from;

		System.arraycopy(array, from, tmpArray, 0, middle - from + 1);

		for (int i = 0; i < to - middle; i++) {
			tmpArray[to - from - i] = array[middle + i + 1];
		}

		int range = to - from + 1;
		while (k < range) {
			if (tmpArray[leftIndex] - tmpArray[rightIndex] < 0) {
				array[k + from] = tmpArray[leftIndex++];
			} else {
				array[k + from] = tmpArray[rightIndex--];
			}
			k++;
		}

	}

}