Assignment 14 - Merge Sort Test

/*

Merge Sort

*/

import java.util.Random;

public class MergeSort
{
private int[] data; //array of values
private static Random generator = new Random();

//create array of given size and fill with random integers
public MergeSort( int size )
{
data = new int[size]; //create space for array

//fill array with random ints range 10-99
for( int i = 0; i < size; i++ )
data[i] = 10 + generator.nextInt( 90 );
}

//calls recursive split method to begin merge sorting
public void sort()
{
sortArray( 0, data.length - 1); //split entire array
}

//splits array, sort subarrays and merges subarrays into sorted array
private void sortArray( int low, int high )
{
//test case: size of array equals 1
if( ( high - low ) >= 1 ) //if not base case
{
int middle1 = (low + high )/2; //calculate middle of array
int middle2 = middle1 + 1; //calculate next element over

//output split step
System.out.println( "split: " + subarray( low, high ) );
System.out.println( " " + subarray( low, middle1 ) );
System.out.println( " " + subarray( middle2, high ) );

//split array in half; sort each half of array
sortArray( low, middle1 ); //first half of array
sortArray( middle2, high ); //second half of array

//merge 2 sorted arrays after split calls return
merge( low, middle1, middle2, high );
}
}

//merge 2 sorted subarrays into one sorted sub array
private void merge( int left, int middle1, int middle2, int right )
{
int leftIndex = left; //index into left subarray
int rightIndex = middle2; //index into right subarray
int combinedIndex = left; //index into temp. work array
int[] combined = new int[data.length]; //working array

//output 2 subarrays before merging
System.out.println( "merge: " + subarray( left, middle1 ) );
System.out.println( " " + subarray( middle2, right ) );

//merge arrays until reaching end of either
while( leftIndex <= middle1 && rightIndex <= right )
{
//place smaller of 2 current elements into result
//and move to next space in arrays
if( data[leftIndex] <= data[rightIndex] )
combined[combinedIndex++] = data[leftIndex++];
else
combined[combinedIndex++] = data[rightIndex++];
}

//if array is empty
if( leftIndex == middle2 )
//copy in rest of right array
while( rightIndex <= right )
combined[combinedIndex++] = data[rightIndex++];
else
//copy in rest of left array
while( leftIndex <= middle1 )
combined[combinedIndex++] = data[leftIndex++];

//copy values back into original array
for( int i = left; i <= right; i++ )
data[i] = combined[i];

//output merged array
System.out.println(" " + subarray( left, right ) );
System.out.println();

}

//method to output certain values in array
public String subarray( int low, int high )
{
StringBuilder temporary = new StringBuilder();

//output spaces for alignment
for( int i = 0; i < low; i++ )
temporary.append( "" );

//output elements left in array
for( int i = low; i <= high; i++ )
temporary.append( "" + data[i] );

return temporary.toString();
}

//method to output values in array
public String toString()
{
return subarray( 0, data.length - 1 );
}
}


--------------------------------------------------------------------------



/*

main function

*/

public class MergeSortTest
{
public static void main( String[] args )
{
//create object to perform merge sort
MergeSort sortArray = new MergeSort(10);

//print unsorted array
System.out.println( "Unsorted: " + sortArray + "\n" );

sortArray.sort(); //sort array

//print sorted array
System.out.println( "Sorted: " + sortArray );
}
}