简单实现MergeSort_JAVA_编程开发_程序员俱乐部

public class MergeSort {

	public static void main(String[] args) {

		MergeSort ms = new MergeSort();
		// int[] a = ms.merge(3, 2);
		// a = ms.merge(2, 3);

		int[] b = { 1, 2, 3, 4, 5, 6 };
		int[] c = { 4, 5, 6, 7, 6, 354, 7542, 61, 34, 67, 8, 3, 4, 8, 1, 4, 6,
				89, 2, 3, 4, 7, 234, 545, 2, 34, 8 };
		long start = System.currentTimeMillis();
		c = ms.sort(c);
		long end = System.currentTimeMillis();
		System.out.println("MergeSort a array with lenght of " + c.length
				+ " in " + (end - start) + " second");
		for (int i = 0; i < c.length; i++) {
			System.out.println(c[i]);
		}

	}

	private int[] sort(int[] number) {
		int dividPoint = number.length / 2;// 4-2 5-2;
		// int secondPart = firstPart+1;

		int[] sortedArray = null;
		int[] firstArray = getArray(number, 0, dividPoint);
		int[] secondArray = getArray(number, dividPoint, number.length);

		// secondArray = divid(secondArray);

		if (firstArray.length > 2) {
			firstArray = sort(firstArray);
		} else if (firstArray.length <= 2) {
			firstArray = merge(firstArray);
		}

		if (secondArray.length > 2) {
			secondArray = sort(secondArray);
		} else if (secondArray.length <= 2) {
			secondArray = merge(secondArray);
		}
		sortedArray = merge(firstArray, secondArray);

		return sortedArray;
	}

	private int[] getArray(int[] arr, int start, int end) {
		int[] subArray = new int[end - start];
		int subindex = 0;
		for (int index = start; index < end; index++) {
			subArray[subindex] = arr[index];
			subindex++;
		}
		return subArray;
	}


	private int[] merge(int i, int j) {
		int[] array = new int[2];
		if (i > j) {
			array[0] = j;
			array[1] = i;
		} else {
			array[0] = i;
			array[1] = j;
		}
		return array;
	}

	private int[] merge(int[] i) {
		int[] returnArr = null;
		if (i.length == 1) {
			returnArr = merge(i[0]);
		}
		if (i.length == 2) {
			returnArr = merge(i[0], i[1]);
		}
		return returnArr;
	}

	private int[] merge(int i) {
		int[] array = new int[1];
		array[0] = i;
		return array;
	}


	private int[] merge(int[] i, int[] j) {
		int[] array = new int[i.length + j.length];
		int pointi = 0;
		int pointj = 0;
		for (int index = 0; index < array.length; index++) {
			if (pointi < i.length && pointj < j.length) {
				if (i[pointi] <= j[pointj]) {
					array[index] = i[pointi];
					pointi++;
				} else {
					array[index] = j[pointj];
					pointj++;
				}
			} else {
				if (pointi == i.length && pointj < j.length) {
					int addedIndex = i.length + pointj - 1;
					for (int newIndex = addedIndex + 1; newIndex < array.length; newIndex++) {
						array[newIndex] = j[pointj];
						pointj++;
					}
					break;
				}
				if (pointi < i.length && pointj == j.length) {
					int addedIndex = j.length + pointi - 1;
					for (int newIndex = addedIndex + 1; newIndex < array.length; newIndex++) {
						array[newIndex] = i[pointi];
						pointi++;
					}
					break;
				}
			}

		}

		return array;
	}
}