package cse0214;
import java.util.*;
////////////////////////////////////////////
class MergeSort{
    double [] data;
    int n;
    int counter1, counter2;

    MergeSort(int total){
        n= total;
        data=new double [n];
        counter1=0;
        counter2=0;
    }//mergersort initial
void dataInput()
{
    Scanner s= new Scanner (System.in);
    System.out.println("Enter "+ n + " data");
    for(int i=0; i<n;i++)
        data[i]=s.nextDouble();
}////end of dataInput

void printArray()
{
    System.out.println("currrent data are");
    for(int i=1; i<n;i++)
        System.out.print(data[i]+ "\t");
    System.out.println();
}//end of printArray

void divide(int left, int right)
{
    if(left< right)
    {
         int mid = (left+right)/2;
         divide(left, mid);
         divide(mid+1, right);

         merge(left, mid, right );

    }//end of if







}//end of divide

 void  merge(int left, int mid,int right)
    {
        int leftbegin =left;
        int leftend= mid;


        int rightbegin= mid+1;
        int rightend= right;

        int n1= leftend - leftbegin + 1;
        int n2= rightend - rightbegin + 1;

        //////temp arrray
        double L[]= new double[n1];
        double R[] = new double[n2];

        //copy to temp array
        for(int i = 0; i<n1; i++)
            L[i] = data [leftbegin + i];


         for(int j = 0; j<n2; j++)
            R[j] = data [rightbegin + j];

         int i = 0, j = 0, k = leftbegin;

         while(i<n1 && j<n2)
         {
              if(L[i]<=R[j])
              {
                  data[k] = L[i];
                  i++;
                  k++;

              }
              else{
              data[k] = R[j];
                  j++;
                  k++;
              }
            }///end of while loop
              ///copy remaining data if any
              while(i<n1)
              {

                      data[k] =L[i];
                      i++;
                      k++;

              }
              while(j<n2)
              {

                      data[k] =R[j];
                      j++;
                      k++;

              }


    }//end of merge method

 void sort(){
     divide(0,n-1);
 }
}////end of mergesort







////////////////////////////////////////////////


public class MyProgram {


    public static void main(String[] args) {

        Scanner s= new Scanner(System.in);
        int total;
        System.out.println("How many data?");
        total=s.nextInt();
        MergeSort a=new MergeSort(total);
        a.dataInput();
        a.printArray();
        System.out.println("After merge sort");
        a.sort();
        a.printArray();
    }

}