import java.util.*;
import java.io.*;
public class MergeSort
{
public static void mergeSort(double[] a, int length)
{
Sort(a, 0, a.length - 1);
}
public static void Sort(double[] a, int left, int right)
{
if (left < right)
{
int mid = (left + right) / 2;
// sort the first and the second half
Sort(a, left, mid);
Sort(a, mid + 1, right);
merge(a, left, mid, right);
}
}
public static void merge(double[] a, int left, int mid, int right)
{
double[] b = new double[right - left + 1]; // merge both halves into a temporary array b
int index1 = left; // next element to consider in the first range
int index2 = mid + 1;
int last = right;
int index = 0; // next open position in b
// as long as neither i1 nor i2 past the end, move the smaller into b
while(index1 <= mid && index2 <= last)
{
if(a[index1] < a[index2])
{
b[index] = a[index1];
index1++;
}
else
{
b[index] = a[index2];
index2++;
}
index++;
}
// note that only one of the two while loops
// below is executed
// copy any remaining entries of the first half
while (index1 <= mid)
{
b[index] = a[index1];
index1++;
index++;
}
// copy any remaining entries of the second half
while (index2 <= last)
{
b[index] = a[index2];
index2++;
index++;
}
int s = 0;
// copy back from the temporary array
for(int i = left; i <= right; i++)
{
a[i] = b[s];
s++;
}
}
public static void main(String[] args)throws FileNotFoundException
{
Scanner input = new Scanner(new FileReader("input.txt"));
int count = 0;
int numOfElements = 0;
double[] array = new double[10];
while(input.hasNextDouble())
{
array[count] = input.nextDouble();
count++;
}
System.out.println("Unsorted Array");
for(int i = 0; i < count; i++)
{
System.out.print(array[i] + " ");
}
System.out.println();
mergeSort(array, array.length);
System.out.println("Sorted Array");
for(int i = 0; i < count; i++)
{
System.out.print(array[i] + " ");
}
input.close();
}
}