public static void sort(Object[] a) {
Object aux[] = (Object[])a.clone();
mergeSort(aux, a, 0, a.length);
}
/**
* Sorts the specified range of the specified array of objects into
* ascending order, according to the <i>natural ordering</i> of its
* elements. All elements in this range must implement the
* <tt>Comparable</tt> interface. Furthermore, all elements in this range
* must be <i>mutually comparable</i> (that is, <tt>e1.compareTo(e2)</tt>
* must not throw a <tt>ClassCastException</tt> for any elements
* <tt>e1</tt> and <tt>e2</tt> in the array).<p>
*
* This sort is guaranteed to be <i>stable</i>: equal elements will
* not be reordered as a result of the sort.<p>
*
* The sorting algorithm is a modified mergesort (in which the merge is
* omitted if the highest element in the low sublist is less than the
* lowest element in the high sublist). This algorithm offers guaranteed
* n*log(n) performance, and can approach linear performance on nearly
* sorted lists.
*
* @param a the array to be sorted.
* @param fromIndex the index of the first element (inclusive) to be
* sorted.
* @param toIndex the index of the last element (exclusive) to be sorted.
* @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
* @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
* <tt>toIndex > a.length</tt>
* @throws ClassCastException if the array contains elements that are
* not <i>mutually comparable</i> (for example, strings and
* integers).
* @see Comparable
*/
public static void sort(Object[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
Object aux[] = (Object[])a.clone(); // Optimization opportunity
mergeSort(aux, a, fromIndex, toIndex);
}
private static void mergeSort(Object src[], Object dest[],
int low, int high) {
int length = high - low;
// Insertion sort on smallest arrays
if (length < 7) {
for (int i=low; i<high; i++)
for (int j=i; j>low &&
((Comparable)dest[j-1]).compareTo((Comparable)dest[j])>0; j--)
swap(dest, j, j-1);
return;
}
// Recursively sort halves of dest into src
int mid = (low + high)/2;
mergeSort(dest, src, low, mid);
mergeSort(dest, src, mid, high);
// If list is already sorted, just copy from src to dest. This is an
// optimization that results in faster sorts for nearly ordered lists.
if (((Comparable)src[mid-1]).compareTo((Comparable)src[mid]) <= 0) {
System.arraycopy(src, low, dest, low, length);
return;
}
// Merge sorted halves (now in src) into dest
for(int i = low, p = low, q = mid; i < high; i++) {
if (q>=high || p<mid && ((Comparable)src[p]).compareTo(src[q])<=0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
}
/**
* Swaps x[a] with x[b].
*/
private static void swap(Object x[], int a, int b) {
Object t = x[a];
x[a] = x[b];
x[b] = t;
} |
