import java.util.Arrays;
import java.util.List;

public class sort {

        public static void main(String[] args) {
                int[] list1 = new int[10000];   
//System.currentTimeMillis() grabs the current /time of day, measured in milliseconds.
            long starttime = System.currentTimeMillis();
            long endtime = 0;

                generate(list1);
                mergeSort(list1);
                printArray(list1);
            endtime = System.currentTimeMillis();
            System.out.println(" ");
            System.out.println("The time is " + ( endtime - starttime));

               
        }
        //Printing Array
        public static void printArray( int x []){
                for (int i=0;i<x.length;i++ ){
                        System.out.print(x[i]+ "  ");
                        }
                        }
        //Generate random list
        public static void generate(int x []){
                for (int i=0;i<x.length;i++ ){
                        x[i]=(int)(Math.random()*10000+1);
                        }
                        }
        //Selection Sorting
        public static void selectionSort2(int[] x) {
            for (int i=0; i<x.length-1; i++) {
                int minIndex = i;      // Index of smallest remaining value.
                for (int j=i+1; j<x.length; j++) {
                    if (x[minIndex] > x[j]) {
                        minIndex = j;  // Remember index of new minimum
                    }
                }
                if (minIndex != i) {
                    //...  Exchange current element with smallest remaining.
                    int temp = x[i];
                    x[i] = x[minIndex];
                    x[minIndex] = temp;
                }
            }
        }
    //Bubble sorting
        public static void bubbleSort1(int[] x) {
                    int n = x.length;
                    for (int pass=1; pass < n; pass++) {  // count how many times
                        // This next loop becomes shorter and shorter
                        for (int i=0; i < n-pass; i++) {
                            if (x[i] > x[i+1]) {
                                // exchange elements
                                int temp = x[i];  x[i] = x[i+1];  x[i+1] = temp;
                            }
                        }
                    }
                }
                //Merge Sort
        public static int[] mergeSort(int[] list)
                {
                        return mergeSort(list, 0, list.length-1);              //start recurssion
                }
               
        private static int[] mergeSort(int[] list,int start, int end)
                {
                        if(start >= end)
                                return new int[]{};               //too many splits (return unsortable array)
                       
                        int mid = (start + end)/2;            //middle point
                       
                        mergeSort(list,start,mid);            //split up left  half
                        mergeSort(list,mid+1,end);            //split up right half
                       
                        //start sorting
                        int left_end    = mid;
                        int right_start = mid + 1;
                       
                        while((start<=left_end)&&(right_start<=end))
                        {
                    if (list[start] >= list[right_start])              //left most element of Left side > left most element of Right side
                    {
                                        int temp = list[right_start];
                                       
                        for(int i=right_start-1;i>=start;i--)
                        {
                            list[i+1] = list[i];                                //shift elements
                        }
                        list[start] = temp;                              //insert element where it belongs
                        mid++; right_start++;               //advance counters
                    }
                    start++;                                    //advance in either case
                }       
                        return list;
                }
                //Binary Search
                 public static void binary_search(int[ ] array, int lowerbound, int upperbound, int key)
                   {
                       int position;
                       int compare_count = 1;

                     // calculate initial search position.
                     position = ( lowerbound + upperbound) / 2;

                     while((array[position] != key) && (lowerbound < upperbound))
                     {
                         compare_count++;
                         if (array[position] > key) // if the value in the search position is greater than the number for ..
                         {                                                  // which we are searching, change upperbound to
                              upperbound = position - 1;   // search position minus one.
                         }                                                             
                              else                                                   
                        {                                                       
                              lowerbound = position + 1; // Else, change lowerbound to search position plus one.
                        }
                       position = (lowerbound + upperbound) / 2;
                     }
                     if (lowerbound < upperbound)
                     {
                           System.out.println("A binary search found the number in " + compare_count + "comparisons.");
                           System.out.println("The number was found in array subscript" + position);
                     }
                     else
                          System.out.println("Number not found by binary search after " +compare_count
                                                                           + " comparisons.");
                  }
//Sequential search
         public static void Find(int[] x,int y)
                 { 
                         boolean found = false;
                  for (int i = 0; i < x.length; i++)
                  {
                         if (x[ i ]  == y)
                        {
                                 found = true;     
                                 break;
                         }
                   }

                  if (found)   //When found is true, the index of the location of key will be printed.
                  {
                        System.out.println("Found " + y + " at index " + x + ".");
                  }
                  else
                  {
                        System.out.println(y + " is not in this array.");
                  }
              }

                       
}