Here is the code with out HTML
formatting. Save it to a file.
/*
* @(#)ExtraStorageMergeSortAlgorithm.java 1.0 97/01/09 Jack Snoeyink
*
* Copyright (c) 1995 University of British Columbia
*
* Permission to use, copy, modify, and distribute this software
* and its documentation for NON-COMMERCIAL purposes and without
* fee is hereby granted provided that this copyright notice
* appears in all copies. Please refer to the file "copyright.html"
* for further important copyright and licensing information.
*
* UBC MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
* THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
* TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
* PARTICULAR PURPOSE, OR NON-INFRINGEMENT. UBC SHALL NOT BE LIABLE FOR
* ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
* DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
*/
/**
* A merge sort demonstration algorithm using extra space
* SortAlgorithm.java, Thu Oct 27 10:32:35 1994
*
* @author Jack Snoeyink@cs.ubc.ca
* @version 1.0, 09 Jan 97
*/
class ExtraStorageMergeSortAlgorithm extends SortAlgorithm {
void sort(int a[], int lo, int hi, int scratch[]) throws Exception {
if (lo >= hi) {
return; /* a[lo] is sorted already */
}
int mid = (lo+hi) / 2;
sort(a, lo, mid, scratch); /* Sort sublist a[lo..mid] */
sort(a, mid+1, hi, scratch); /* Sort sublist a[mid+1..hi] */
int k, t_lo = lo, t_hi = mid+1;
for (k = lo; k <= hi; k++) /* Merge sorted sublists */
if ((t_lo <= mid) && ((t_hi > hi) || (a[t_lo] < a[t_hi]))) {
scratch[k] = a[t_lo++];
pause(t_lo, t_hi);
}
else {
scratch[k] = a[t_hi++];
pause(t_lo, t_hi);
}
for (k = lo; k <= hi; k++) {
a[k] = scratch[k]; /* Copy back to a */
pause(k);
}
}
void sort(int a[]) throws Exception {
int scratch[] = new int[a.length];
sort(a, 0, a.length-1, scratch);
}
}
Return to
Sorting Algorithms Demo