www.pudn.com > GMapViewer-src.zip > Sort.java

package org.sreid.j2me.util;

/*
 * Sort algorithm implementation with no external dependencies except 
 * org.sreid.j2me.util.Comparator and java.lang.System.arraycopy. The
 * algorithm used is mergesort, as in J2SE.
 */
public final class Sort {

	// All methods are static, no need to construct.
	private Sort() { }


	/**
	 * Sorts the specified list using the specified comparator.
	 */
	public static void sort(Object[] list, Comparator cmp) {
		mergeSort(list, 0, list.length, cmp, new Object[list.length]);
	}

	/**
	 * Sorts elements in the specified list between fromIndex (inclusive) and 
	 * toIndex (exclusive) using the specified comparator.
	 */
	public static void sort(Object[] list, int fromIndex, int toIndex, Comparator cmp) {
		mergeSort(list, fromIndex, toIndex, cmp, new Object[toIndex - fromIndex]);
	}


	private static void mergeSort(Object[] list, int start, int end, Comparator cmp, Object[] tmplist) {
		int len = end - start;
		if (len <= 1) return; // Single element, no sorting required. This is the bottom of the recursion tree.

		// Divide the list into two halves, then sort the two halves. This is the recursive part.
		int mid = start + (len / 2);
		mergeSort(list, start, mid, cmp, tmplist);
		mergeSort(list, mid, end, cmp, tmplist);

		// This simple check tells us if the list is already sorted. If so, we can skip the merge operation.
		if (cmp.compare(list[mid - 1], list[mid]) <= 0) return;

		// Merge the two sorted halves into a new sorted list
		int itl; // index in tmplist
		int i1; // index in first half of list
		int i2; // index in second half of list
		for (itl = 0, i1 = start, i2 = mid; i1 < mid && i2 < end; itl++) {
			// Grab the next item, either from the first half or the second (whichever has the smaller item).
			// Using ++ to increment whichever index we used.
			tmplist[itl] = ( cmp.compare(list[i1], list[i2]) <= 0 ? list[i1++] : list[i2++] );
		}
		// One of the two halves has run out of items. Just copy the remainder from the other half.
		// One of these two copies will be a no-op (copy 0 items).
		System.arraycopy(list, i1, tmplist, itl, mid - i1);
		System.arraycopy(list, i2, tmplist, itl, end - i2);

		// Copy the sorted list into the original list, and we're done.
		System.arraycopy(tmplist, 0, list, start, len);
	}
}