import java.util.ArrayList;
 
public class Sort
{
    int i;
    int j;
    //make arraylist
    ArrayList<Integer> a = new ArrayList();
    // count how many iterations are performed during the sort
    private long iterations = 0;
 
    public ArrayList<Integer> selectionSort(ArrayList<Integer> a) 
    {
        //checks every other number and gives one the name i and 1 j
        for (int i=0; i < a.size()-1; i++)
        {
 
        for (int j=i+1; j < a.size(); j++) 
        {
            //check to see which is greater to put them in order
            if (a.get(i) > a.get(j)) 
            {
                //If x is the greater element, exchange elements
                int temp = a.get(i);
                a.add(i,a.get(j));
                a.add(j,temp);
                //iterations++;
            }
            iterations++;
        }
    }
    System.out.println("Selection sort took " + iterations + " iterations.");
    //return list
    return a;
}
}
 
import java.util.ArrayList;
public class Sorter
{
//declare as integers
    private int mergesort = 0;
    private int merge = 0;
    public ArrayList Sort(ArrayList<Integer> a)
    {
        //just make sure they're all zero\
       //uses method from bottom
        while(!leastToGreatest(a))
        {
            for(int x = 0; x < a.size() - 1; x++)
            {
                if (a.get(x) > a.get(x+1))
                //use change method below and sort    
                a = change(a, x);
            }
        }
        return a;
    }
    // make a temporary instance and make instances of positions
    private ArrayList change(ArrayList<Integer> a, int position)
    {
        int temp = a.get(position);
        a.set(position, a.get(position+1));
        a.set(position+1, temp);
        return a;
    }
    private boolean leastToGreatest(ArrayList<Integer> a)
    {
        for(int x = 1; x < a.size(); x++)
        {
            //put ArrayList in order using this loop
            if(a.get(x) < a.get(x-1))
                return false;
        }
        return true;
    }
    // make array to hold positions
    public int[] getData()
    {
        return new int[] {mergesort, merge};
    }
 
 
 
 
    //LAB
    public ArrayList<Integer> MergeSort(ArrayList<Integer> a)
    {
        mergesort++;
        // make 3 lists to make merging easier
        ArrayList<Integer> result = new ArrayList<Integer>();
        ArrayList<Integer> left = new ArrayList<Integer>();
        ArrayList<Integer> right = new ArrayList<Integer>();
        //already sorted in this case
        if(a.size() <= 1)
            return a;
        else
        {
            //perform these loops if arraylist is unsorted
            int half = a.size() / 2;
            for (int x = 0; x < half; x++)
            {
                left.add(a.get(x));
            }
            for (int x = half; x < a.size(); x++)
            {
                right.add(a.get(x));
            }
            left = MergeSort(left);
            right = MergeSort(right);
            result = Merge(left, right);
            return result;
        }
    }
 
    private ArrayList<Integer> Merge(ArrayList<Integer> left, ArrayList<Integer> right)
    {
        //merge method used to complete sorting
        merge++;
        ArrayList<Integer> result = new ArrayList<Integer>();
        //has to be greater than 0 otherwise no merging is needed
        while(left.size() > 0 && right.size() > 0)
        {
            //put the lower numbers on the left
            if (left.get(0) <= right.get(0))
            {
                result.add(left.get(0));
                left.remove(0);
            }
            else
            {
                result.add(right.get(0));
                right.remove(0);
            }
        }
        //put the higher numbers on the right
        if ( left.size() > right.size())
            result.addAll(left);
        else if (left.size() <= right.size())
            result.addAll(right);
        return result;
    }    
}
 
 
import java.util.*;
import java.io.*;
public class test
{
// main 
    public static void main(String[] args)
    {
       // make longs for timestamps
        long begin, end;
        //import scanner for user input
        Scanner userinput = new Scanner(System.in);
        System.out.println("Large file?");
        String input = userinput.nextLine();
        String first = "";
        String outputFile = "";
        String outputFile2 = "";
        //create if statement to determine whether user wants a small text file or a large one
        if(input.equalsIgnoreCase("yes"))
        {
            // read in file
            first = "H:\\Computer Science 160\\Lab 9\\Large.txt";
            outputFile = "H:\\largeSorted.txt";
            outputFile2 = "H:\\largeSelectionSort.txt";
        }
        else if (input.equalsIgnoreCase("no"))
        {
            //read in file
            first = "H:\\Computer Science 160\\Lab 9\\small.txt";
            outputFile = "H:\\smallSorted.txt";
            outputFile2 = "H:\\smallSelectionSort.txt";
        }
        try
        {
            //apply sorting method
            Scanner scn = new Scanner(new File(first));
            Sorter s = new Sorter();
            Sort sort = new Sort();
            //use arraylist
            ArrayList<Integer> p = new ArrayList();
            while (scn.hasNext())
            {
                p.add(scn.nextInt());
            }
 
            //INSERT TIME CALCULATION STUFF
            begin = System.currentTimeMillis();
            p = s.MergeSort(p);
            end = System.currentTimeMillis();
            //print back the output placed in the new file
            PrintWriter output = new PrintWriter(new FileWriter(outputFile));
            // get the entire size
            for(int x = 0; x < p.size(); x++)
                output.println(p.get(x));
            System.out.println("Merge sort done!");
            System.out.println("MergeSort calls: " + s.getData()[0] + "\nMerge Calls: " + s.getData()[1]);
            System.out.println("Time Elapsed: " + (end - begin) + " Milliseconds");
            output.close();
            begin = System.currentTimeMillis();
            p = sort.selectionSort(p);
            end = System.currentTimeMillis();
            //print out the second sort for merge
            PrintWriter output2 = new PrintWriter(new FileWriter(outputFile2));
            for(int x = 0; x < p.size(); x++)
                output2.println(p.get(x));
            System.out.println("Time Elapsed: " + (end - begin) + " Milliseconds");
            output2.close();
        }
        //catch a general exception for ease
        catch (Exception e)
        {
            System.out.println(e);
        }
    }
}