/** This program is intended to be used with the book "Java 6 -- What Do You Want To Do?"
 * by Steven P. Warr and is distributed free of charge and without and expectations of remuneration.
 * Chapter ALG   NOTE all program names begin with the the title of the chapter in which
 * they are intended to be used.   Copyright 2010 Steven P. Warr All rights reserved
 */

import java.io.*;   		// needed so you can use the File class
import java.util.*;  		//needed for Scanner
public class Alg09
{
	public static void main(String[ ] args) throws IOException
		{
		     int numItems = 0;
			 int x = 0;
			 File filename = new File("nameOfFile.data");  
			 Scanner inFile = new Scanner(filename);
			 while(inFile.hasNext())  // This loop counts the items in the file
					{                 // so that the array can be dimensioned
						inFile.nextDouble();  //to the correct size
						x++;
					}	
			 inFile.close();		
			 numItems = x;		
             double [ ]price = new double [numItems]; 	//Dimension the array to numItems.
			 x = 0;		                       			// reinitialize LCV
			 inFile = new Scanner(filename);   			//reset data file to beginning
			 while(inFile.hasNext())
					{
				          price[x] = inFile.nextDouble( );  // read one item and 
 				   											//point to the next one.
					      x ++;  				// add one so there is a new index.
					}
			 inFile.close();		
             System.out.println("\nOriginal list\n");
		     for(int c = 0;c < price.length ; c++)   
				System.out.println(c + ". " + String.format("%7.2f",price[c]));  
             mergeSort(price);
             System.out.println("\nSorted list\n");
		     for(int c = 0;c < price.length ; c++)   
				System.out.println(c + ". " + String.format("%7.2f",price[c]));  
        }
    public static void mergeSort(double [] list)
    {
    	if (list.length <= 1)                    //base case - ends recursion
    		return;
    	double[] first = new double [list.length /2];	  //Make two new arrays
    	double[] second = new double [list.length - first.length];   
    	copy(list, 0, first,0,first.length);						//copy the first half of the array list to first 
    	copy(list, first.length, second, 0,second.length);	        //copy the second half of the array to second
    	mergeSort(first);   			// recursive case
    	mergeSort(second);  			// recursive case
    	merge(list,first,second);       //  
    }	    
    public static void merge(double [] list, double[] first, double[] second)
    {
    	int iFirst = 0;
    	int iSecond = 0;
    	int y = 0;
    	while (iFirst < first.length && iSecond < second.length)
    		{
    			if ( first[iFirst] < second[iSecond])
    				{
    					list[y] = first[iFirst];
    					iFirst++;
    				}
    			else
    				{
    					list[y] = second[iSecond];
    					iSecond++;
    				}
                y++;
    		}
		copy(first, iFirst, list, y, first.length - iFirst);				
		copy(second, iSecond, list, y, second.length - iSecond);				
    		
    }
    public static void copy(double[] src, int srcStart, double [] tgt,int tgtStart, int len)			
    {
    	for (int x = 0; x<len; x++)
    	    tgt[x+tgtStart] = src[x + srcStart]; 
    }	
}