mergesort.java

国外的数据结构与算法分析用书

public class MergeSort
{
	/**	Sort array keys using the recursive merge sort approach. */
	public void mergeSortRecursive(int[ ] keys)
	{
		int[ ] temp = new int[keys.length];
		mergeSortHelper(keys, temp, 0, keys.length - 1);
	}

	/**	A helper method to perform a recursive merge sort on the part of the
		array between start and finish. */
	private void mergeSortHelper(int[ ] inVec, int[ ] temp, int start, int finish)
	{
		int size = finish - start + 1; // number of items in current sequence
		if (size > 1)
		{
			int middle = (start + finish) / 2; // find position of middle item
			mergeSortHelper(inVec, temp, start, middle); // sort first subsequence
			mergeSortHelper(inVec, temp, middle + 1, finish); // sort second subsequence
			merge(inVec, temp, start, middle + 1, finish); // merge two sorted subsequences
		}
	}

	/**	Merge start1st through start2nd-1 with start2nd through end2nd in array inVec
		using temp as a temporary array */
	private void merge(int[] inVec, int [] temp, int start1st, int start2nd, int end2nd)
	{
		int cur1, cur2; // indices of the current items of each sequence
		int cur3; // index of the next location of temp

		temp = new int[end2nd - start1st + 1]; // create temporary storage for new sequence
		cur1 = start1st;
		cur2 = start2nd;
		cur3 = 0;

		while((cur1 < start2nd) && (cur2 <= end2nd))
		{
			if(inVec[cur1] <= inVec[cur2])
				temp[cur3] = inVec[cur1++];
			else
				temp[cur3] = inVec[cur2++];
			cur3++;
		}
		while(cur1 < start2nd) // copy remainder of first (if any) sequence into temp
			temp[cur3++] = inVec[cur1++];

		while(cur2 <= end2nd) // copy remainder of first (if any) sequence into temp
			temp[cur3++] = inVec[cur2++];

		cur1 = start1st;
		cur3 = 0;
		while(cur1 <= end2nd) // copy items from temp back into inVec
			inVec[cur1++] = temp[cur3++];
	}
}