二路归并排序

二路归并排序：将两个按值有序序列合并成一个按值有序序列

 

排序基本思想是：

     申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

      设定两个指针，最初位置分别为两个已经排序序列的起始位置

      比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

      重复步骤3直到某一指针达到序列尾

      将另一序列剩下的所有元素直接复制到合并序列尾

 

public class TwoWayMergeSort {
	/**
	 * 二路归并排序
	 * @param data1
	 * @param data2
	 * @return
	 */
	public static int[] two_way_mergeSort(int[] data1, int[] data2) {
		int[] temp = new int[data1.length + data2.length];
		int i = 0, j = 0, iter = 0;
		for (; i < data1.length && j < data2.length;) {
			if (data1[i] <= data2[j]) {
				temp[iter] = data1[i];
				iter++;
				i++;
			} else {
				temp[iter] = data2[j];
				iter++;
				j++;
			}
		}
		for (; i < data1.length; i++, iter++) {
			temp[iter] = data1[i];
		}
		for (; j < data2.length; j++, iter++) {
			temp[iter] = data2[j];
		}
		return temp;
	}
	
	public static void main(String[] args) {
		int[] v1 = { 1, 2, 4, 8};
		int[] v2 = {3, 5, 6,7 };
		int[] v = TwoWayMergeSort.two_way_mergeSort(v1, v2);

		for (int key : v) {
			System.out.format(" %d", key);
		}
	}
}