<![CDATA[
// insertionSort and mergeSort adapted from Jason Harrison and Jack Snoeyink
// see http://www.cs.ubc.ca/spider/harrison/Java/
// smartMergeSort and main by Gary Yngve
import java.util.*;
public class SortingDemo {
public static void insertionSort(int[] a) {
insertionSort(a,0,a.length-1);
}
private static void insertionSort(int[] a, int lo, int hi) {
for (int i = lo+1; i <= hi; i++) {
int j = i; // invariant: everything <i is in sorted order
int tmp = a[i];
while ((j > lo) && (a[j-1] > tmp)) { // until at the correct place
a[j] = a[j-1]; // shift one to the right
j--; // walk backward
}
a[j] = tmp; // insert into sorted order
}
}
private static void mergeSort(int[] a, int lo, int hi, int[] work) {
if (lo >= hi)
return; // a[lo] is sorted already
int mid = (lo+hi)/2;
mergeSort(a,lo,mid,work); // Sort sublist a[lo..mid]
mergeSort(a,mid+1,hi,work); // Sort sublist a[mid+1..hi]
int t_lo = lo, t_hi = mid+1;
for (int k = lo; k <= hi; k++) // Merge sorted sublists
if ((t_lo <= mid) && ((t_hi > hi) || (a[t_lo] < a[t_hi])))
work[k] = a[t_lo++];
else
work[k] = a[t_hi++];
for (int k = lo; k <= hi; k++) // Copy work back to a
a[k] = work[k];
}
private static void smartMergeSort(int[] a, int lo, int hi,
int[] work, int stopsize) {
if (hi-lo <= stopsize) {
insertionSort(a,lo,hi); // insertSort is faster here
return;
}
int mid = (lo+hi)/2;
smartMergeSort(a,lo,mid,work,stopsize); // lower half
smartMergeSort(a,mid+1,hi,work,stopsize); // upper half
int t_lo = lo, t_hi = mid+1;
for (int k = lo; k <= hi; k++) // Merge sorted sublists
if ((t_lo <= mid) && ((t_hi > hi) || (a[t_lo] < a[t_hi])))
work[k] = a[t_lo++];
else
work[k] = a[t_hi++];
for (int k = lo; k <= hi; k++)
a[k] = work[k]; // Copy work back to a
}
public static void mergeSort(int[] a) {
int[] work = new int[a.length];
mergeSort(a,0,a.length-1,work);
}
public static void smartMergeSort(int[] a, int stopsize) {
int[] work = new int[a.length];
smartMergeSort(a,0,a.length-1,work, stopsize);
}
public static void main(String[] args) {
int[] a = new int[1<<20];
int[] b,c;
Random r = new Random();
for(int i = 0; i < a.length; i++)
a[i] = r.nextInt(1<<30);
b = (int[])a.clone();
c = (int[])a.clone();
Arrays.sort(c);
long t1=System.currentTimeMillis();
mergeSort(b);
long t2=System.currentTimeMillis();
smartMergeSort(a,8);
long t3=System.currentTimeMillis();
if (!Arrays.equals(a,b)) throw new RuntimeException("sort bug");
if (!Arrays.equals(a,c)) throw new RuntimeException("sort bug");
System.out.println("Merge: " + (t2-t1) + ", SmartMerge: " + (t3-t2));
}
}
]]>