Merge Sort Algorithm

Click on the applet below to see the algorithm run.

/*
 * @(#)MergeSortAlgorithm.java		1.0	97/02/15 Alyce Brady
 * based on @(#)BubbleSortAlgorithm.java	1.6f 95/01/31 James Gosling
 *
 * which had Copyright (c) 1994-1996 Sun Microsystems, Inc. All Rights Reserved.
 *
 * See additional copyright information below.
 *
 *
 * A selection sort demonstration algorithm based on
 * SortAlgorithm.java and
 * SortItem.java.
 *
 */

class MergeSortAlgorithm extends SortAlgorithm
{
    void mergeSort(int a[], int start, int segLength) throws Exception
    {
	// Divide the array segment to be sorted in two and then
	// sort and merge those two.
	int	half = segLength / 2;	// half (rounded down)

	// Sort each of the two sub-segments
	if ( half > 1 )
		mergeSort (a, start, half);
	if ( segLength - half > 1 )
		mergeSort (a, start + half, segLength - half);

	// Copy the two sub-segments and then merge them into the sorted whole
	int	t1[] = new int[half];
	int	t2[] = new int[segLength - half];
	int	i = start;
	for ( int j = 0; j < half; )		// copy 1st half
		t1[j++] = a[i++];
	for ( int j = 0; j < segLength - half; )	// copy 2nd half
		t2[j++] = a[i++];
	merge (a, start, t1, t2);		// merge 2 halves
	pause(start, start+segLength-1);
    }

   void	merge (int a[], int start, int t1[], int t2[]) throws Exception
   {
	int	index = start;
	int	end = start + t1.length + t2.length;
	int	t1index = 0;
	int	t2index = 0;

	pause(start, end-1);
	while ( t1index < t1.length && t2index < t2.length )
	{
		if (stopRequested)
                {   return;
                }

		if ( t1[t1index] <= t2[t2index] )
			a[index] = t1[t1index++];
		else
			a[index] = t2[t2index++];
                pause(index++, end-1);
	}
	while ( t1index < t1.length )
	{
		if (stopRequested)  return;
		a[index] = t1[t1index++];
                pause(index++, end-1);
	}
	while ( t2index < t2.length )
	{
		if (stopRequested)  return;
		a[index] = t2[t2index++];
                pause(index++, end-1);
	}
   }

   public void sort(int a[]) throws Exception
   {
	if ( a.length > 1 )
		mergeSort(a, 0, a.length);
   }
}

/*
 * Permission information for original BubbleSort algorithm:
 *
 * Permission to use, copy, modify, and distribute this software
 * and its documentation for NON-COMMERCIAL or COMMERCIAL purposes and
 * without fee is hereby granted. 
 * Please refer to the file http://java.sun.com/copy_trademarks.html
 * for further important copyright and trademark information and to
 * http://java.sun.com/licensing.html for further important licensing
 * information for the Java (tm) Technology.
 * 
 * SUN 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. SUN SHALL NOT BE LIABLE FOR
 * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
 * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
 * 
 * THIS SOFTWARE IS NOT DESIGNED OR INTENDED FOR USE OR RESALE AS ON-LINE
 * CONTROL EQUIPMENT IN HAZARDOUS ENVIRONMENTS REQUIRING FAIL-SAFE
 * PERFORMANCE, SUCH AS IN THE OPERATION OF NUCLEAR FACILITIES, AIRCRAFT
 * NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL, DIRECT LIFE
 * SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH THE FAILURE OF THE
 * SOFTWARE COULD LEAD DIRECTLY TO DEATH, PERSONAL INJURY, OR SEVERE
 * PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH RISK ACTIVITIES").  SUN
 * SPECIFICALLY DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR
 * HIGH RISK ACTIVITIES.
 */

Original sorting algorithms by:

James Gosling, jag@firstperson.com