CSC 216/s08/prevent error/page2

Source Code

This is a full implementation of Merge Sort in Java. Of the many ways available, this one uses arrays.

package mergeSort;

/**
 * mergeSort is an algorithm for sorting a passed array.
 *
 * @author Eric LIfka
 * @version 1.0
 */
public class MergeSort{
	
	/**
	 * merge takes two arrays as parameters and returns a sorted array.
	 *
	 * @param left - one of two arrays to be merged
	 * @param right - the other array to be merged
	 * @return result - the resulting array
	 */
	public int[] merge(int[] left, int[] right){
		// Initialize numbers to be used in the merge algorithm
		int leftLength = left.length;
		int rightLength = right.length;
		int leftLocation = 0;
		int rightLocation = 0;
        int resultLocation = 0;
		
		// Initialize result array to joint length of left and right
		int[] result = new int[leftLength + rightLength];
		
		// the merge algorithm
		
		// goes through the two arrays adding values to result from smallest to largest
		while (leftLocation < leftLength && rightLocation < rightLength){
			if (left[leftLocation] < right[rightLocation]){
				result[resultLocation] = left[leftLocation];
                resultLocation ++;
                leftLocation ++;
			} else {
                result[resultLocation] = right[rightLocation];
                resultLocation ++;
                rightLocation ++;
            }
		}
		// these two while loops add whatever's left of the two arrays to the end of result
        while (leftLocation < leftLength){
        	result[resultLocation] = left[leftLocation];
            resultLocation ++;
            leftLocation ++;
        }
		while (rightLocation < rightLength){
			result[resultLocation] = right[rightLocation];
			resultLocation ++;
			rightLocation ++;
		}

		// Return the result
		return result;
	}
	
	/**
	 * sort takes an array, separates it into two equal arrays 
	 * and calls itself on the two new arrays, sorting the array
	 * via recursion.
	 *
	 * @param source - the array to be sorted
	 * @return the sorted version of source
	 */
	public int[] sort(int[] source){
		// Check to see if source is size one and return it if so
		if (source.length <= 1){
			return source;
		}

		// Initialize left, right and middle
		int middle = source.length / 2;
		int[] left = new int[middle];
		int[] right = new int[source.length - middle];

		// Run through source separating it into left and right
		for (int length = 0; length < source.length; length++){
			if (length < middle){
				left[length] = source[length];
			} else {
				right[length - middle] = source[length];
			}
		}

		// Call merge on the sorted version of left and right
		return this.merge(this.sort(left), this.sort(right));
	}
}

The class can be utilized via a Driver class. The following is a simple one that calls MergeSort on a randomized array of size 100.

package mergeSort;

import java.util.Random;

/**
 * mergSortTest is a driver class for the mergeSort class.
 * 
 * @author Eric Lifka
 * @version 1.0
 */
public class Driver{
	
	public static void main(String[] args){
		Random r = new Random();
		MergeSort mergeSort = new MergeSort();
		int[] toSort = new int[100];
		for (int k = 0; k < toSort.length; k++){
			toSort[k] = (int)(r.nextDouble()*100);
		}
		int[] sorted = mergeSort.sort(toSort);
		for (int k = 0; k < toSort.length; k++){
			System.out.println(toSort[k] + "     " + sorted[k]);
		}
	}
}