import java.util.Arrays;
public class SortItOut
{
    /**
     * A collection of sorting algorithms 
     * so you can measure how long it takes for 
     * each to sort the same array of random ints
     * 
     * Chris Thiel, ofmcap
     * 27 Jan 2026
     */
    
    private static final int SIZE  = 1000; // how many ints to sort
    
    private static final int N = 100;  //how many repititions of making and sorting an int array
    
    private static int[] temp;// a work area for the merge sort algorithm
    
    
    public static void selectionSort(int[] data)
    {

        for (int i = 0; i < data.length - 1; i++)
        {
            int minIndex = i;
            for (int j = i + 1; j < data.length; j++)
            {
                if (data[j] < data[minIndex])
                {
                    minIndex = j;
                }
            }
            swap(data, i, minIndex );
        }

    }

    public static void insertionSort(int[] data)
    {

        for (int i = 1; i < data.length ; i++)
        {  
            int value = data[i];
            int j = i-1;
            while ( j >= 0 &&  data[j] > value )
            {
                data[j+1] = data[j];
                j--;
            }
            data[j+1] = value;     
        }
    }

    public static void mergeSort(int arr[]){
        int left = 0;
        int right = arr.length-1;
        temp = new int[arr.length];
        mergeSort(arr, left, right);
    }

    private static void mergeSort(int arr[], int left, int right){
        /*  SUBDIVIDE */
        if((right - left) < 2) // base case 
        {
            if(right > left && arr[right] < arr[left])
                swap(arr, right, left);
        } else { // recursive case
            int mid = (left + right)/2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid+1, right);
            /* Bring together */
            merge(arr, left, mid, right);
        }    
    }

    private static void merge(int arr[], int left, int mid, int right){
        int i = left; int j = mid + 1; int k = left;
        /* while both have elements */
        while( i <= mid && j <= right ){
            if (arr[i] < arr[j]){
                temp[k] = arr[i++];  // i++ increment after use ++i inc before use
            } else {
                temp[k] = arr[j++];
            }
            k++;
        }
        /* now we attach remaining elements */
        while( i <= mid )
            temp[k++] = arr[i++];
        while( j <= right )
            temp[k++] = arr[j++];
        /* transfer back to arr */
        for (k = left; k < right; k++)
            arr[k] = temp[k];
    }

    public static void swap(int[] arr, int i, int j)
    {
        /*  missing code d */
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static int[] randomIntArray(){
        int[] arr = new int[ SIZE ];
        for(int i = 0; i <  SIZE ; i++)
            arr[i] = 10 + (int)(90 * Math.random() );
        return arr;
    }

    public static int[] descendingArray( ){
        int[] arr = new int[ SIZE ];
        for(int i = 0; i <  SIZE ; i++)
            arr[i] =  SIZE -i ;
        return arr;
    }

    public static int[] clone(int[] arr){
        int[] arr2 = new int[arr.length];
        for(int i = 0; i < arr.length; i++)
            arr2[i] = arr[i];
        return arr2;
    }

    public static void test(){
        

        long[] sel = new long[N];
        long[] ins = new long[N];
        long[] mer = new long[N];
        for (int reps = 0; reps < N; reps++)
        {

            int[] arr0 = randomIntArray();
            //int[] arr0 = descendingArray( SIZE );
            int[] arr1 = clone(arr0);// only fair to use the same array
            int[] arr2 = clone(arr0);// for each algorithm

            System.out.println("Selection sort Test");

            System.out.println("before: " + Arrays.toString(arr0));
            long start = System.nanoTime();
            selectionSort(arr0);
            sel[reps] = System.nanoTime()- start;
            System.out.println(" after: " + Arrays.toString(arr0));
            System.out.println("That took " + sel[reps] );
            
            System.out.println("Insertion sort Test");
            System.out.println("before: " + Arrays.toString(arr1));
            start = System.nanoTime();
            insertionSort(arr1);
            ins[reps] = (System.nanoTime()-start);
            System.out.println("That took " + ins[reps] );
            System.out.println(" after: " + Arrays.toString(arr1));
            
            System.out.println("Merge sort Test");

            System.out.println("before: " + Arrays.toString(arr2));
            start = System.nanoTime();
            mergeSort(arr2);
            mer[reps] = System.nanoTime()- start;
            System.out.println(" after: " + Arrays.toString(arr2));
            System.out.println("That took " + sel[reps] );
            
        }
        int sWin =0, iWin =0; int mWin = 0;

        for (int i = 0 ; i < N; i++){
            if (sel[i] < ins[i] && sel[i] < mer[i])
                sWin++;
            else if ( ins[i] < mer[i] && ins[i] < mer[i])
                iWin++;
            else 
                mWin++;
            System.out.println( i +". " +sel[i] + " vs " + ins[i] + " vs " + mer[i]);

        }
        System.out.println("Selection sort won "+sWin + " times.");
        System.out.println("Insertion sort won "+iWin + " times.");
        System.out.println("Merge sort won "+mWin + " times.");
    }
}