Program 6

package program6;


import java.util.Random;

// Zach Krizan
// Program #6
// Data Structures

public class Main
{

public static void main(String a[])
{
/***********************************************************
* This program will demonstrate MergeSort.
* It will generate 10,000 random numbers.
* Then it will run a loop to display the first 100.
* It will then sort the numbers.
* Afterward, another loop will run to display the first 100
* numbers after being sorted.
***********************************************************/


System.out.println("Generating 10000 random numbers...");
//creates array named myNums with 10000 places
int myNums[] = new int[10000];

//creates a random object
Random rand = new Random();

//this loop will create the 10000 random numbers
for(int i=0; i {
myNums[i] = rand.nextInt(100);
}

System.out.println();
System.out.println("The first 100 numbers are: ");

//this loop will display the first 100 numbers
for (int j=0; j<101; j++)
{
System.out.print(myNums[j]+" ");
}

System.out.println();
System.out.println();
System.out.println("Sorting...");
mergeSort_srt(myNums,0, myNums.length-1); //runs mergesort method
System.out.println();
System.out.println("First 100 values after being sorted are:");

//this loop will print the first 100 numbers after being sorted
for(int i = 0; i <101; i++)
{
System.out.print(myNums[i]+" ");
}
}

//method mergeSort
public static void mergeSort_srt(int array[],int lo, int hi)
{
//This method will sort the array
//It will split the array in half to sort it

int low = lo;
int high = hi;

//ir low is greater than or equal to high return
if (low >= high)
{
return;
}

int middle = (low + high) / 2; //finds the middle
mergeSort_srt(array, low, middle); //runs mergeSort method
mergeSort_srt(array, middle + 1, high); //runs mergeSort method

int end_low = middle;
int start_high = middle + 1;

//while low is less than or equal to middle or middle + 1 is less than
// or equal to high
while ((lo <= end_low) && (start_high <= high))
{
if (array[low] < array[start_high])
{
low++;
} else
{
int Temp = array[start_high];
for (int k = start_high- 1; k >= low; k--)
{
array[k+1] = array[k];
}
array[low] = Temp;
low++;
end_low++;
start_high++;
}
}
}
}