//Copyright Dr. Marek A. Suchenek, 2015
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package inversions;

/**
 *
 * @author suchenek
 */
public class MergeSort {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
           int[] Array;
           int N;
 for (N = 500; N<=500; N++)
 {
// pseudo-random case generator     
        Array = new int[N];
        for (int i = 0; i < N; i++)
        Array[i] = (int)(Math.sqrt(97)*(13*i + 1)*(19*i + 2)+i - 17)%1000;
// best-case generator        
        for (int i = 0; i < N; i++)
        Array[i] = -i;
// worst-case generator        
        for (int i = 0; i < N; i++)
            Array[i] = i+1;
        unSort(Array, 0, N-1);

//       int[] ReversedArray = new int[N];
//        for (int i = 0; i < N; i++)
//        ReversedArray[i] = Array[N-i -1];
        System.out.println("*** " + N + "-element array to be sorted ***");

       for (int i = 0; i < N; i++) System.out.print(Array[i] + ", ");
        System.out.println();
        Bcnt.clr(); //counts comps while sorting of both arrays
//        cnt2.clr(); //counts shifts while sorting of both arrays
        System.out.println("Sorting Array[" + N + "]");
        Array = Sort(Array, 0, N-1);
        for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
        System.out.println();
        System.out.print("comps(" + N +")");
        Bcnt.outln(" = ");
        System.out.println("Worst-case  W(N) = " + W(N) + " N*MyMath.ceilLg(N) - MyMath.twoToCeilLg(N)+1 = " + (N*MyMath.ceilLg(N) - MyMath.twoToCeilLg(N)+1));
        System.out.println("Best-case  B(N) = " + B(N));
//        System.out.print("shifts(" + N +")");
//        cnt2.outln(" = ");
//        System.out.print("calls(" + N +")");
//        cnt3.out(" = ");
//        cnt.clr(); //counts comparisons while sorting of both arrays
//        cnt2.clr(); //counts shifts while sorting of both arrays

//        System.out.println("Sorting ReversedArray[" + N + "]");
//        Sort(ReversedArray, 0, N-1);
//        for (int i = 0; i < N; i++) System.out.print(ReversedArray[i] + " ");
//        System.out.println();
//        System.out.print("accumulated comps(" + N +")");
//        Bcnt.outln(" = ");
//        System.out.println("  2*N*(N-1)/2 = " + 2*N*(N-1)/2);
//        System.out.print("accumulated shifts(" + N +")");
//        cnt2.outln(" = ");
//        System.out.print("accumulated calls(" + N +")");
//        cnt3.out(" = ");
//        System.out.println("The largest stack was " + cnt3.getMax());
        Bcnt.clr();

 }
}

    private static int[] Merge(int[] A, int[] B)
            // Merges two sorted arrays into one sorted array
{
    int[] C = new int[A.length + B.length];
    int indexA = 0, indexB = 0, indexC = 0;
    while ((indexA < A.length) && (indexB < B.length))
    {
        if (A[indexA] < B[indexB] & Bcnt.incr()) // move A[indexA] to C
            C[indexC++] = A[indexA++];
        else // move B[indexA] to B
            C[indexC++] = B[indexB++];
    }
    // copy the remaining part of A or B to C
    if (indexA < A.length) // copy the remaining part of A
        for (int i = indexA; i < A.length; i++)
            C[indexC++] = A[i];
    else // copy the remaining part of B
        for (int i = indexB; i < B.length; i++)
            C[indexC++] = B[i];
//    cnt2.incr();
    return C;
}

    public static int[] Sort(int[] A, int lo, int hi)
// input constrain: lo <= hi
    {
        if ((hi - lo) == 0)
        {
//            return ({A[lo]});
            int[] C = {A[lo]};
            return C;
        }
        int splitPoint = (lo + hi)/2; // floor of ...
        return Merge(Sort(A, lo, splitPoint), 
                Sort(A, splitPoint + 1, hi));
    }
    

    public static void unSort(int[] A, int lo, int hi)
// turns A onto a worst-case array            
// input constrain: lo <= hi and A is sorted
    {
        if ((hi - lo) <= 1) return; // already worst
        int splitPoint = (lo + hi)/2; // floor of ...
        int max = A[hi]; // will be sent to left array
        for (int i = hi; i > splitPoint; i--)
            A[i] = A[i-1]; //A[hi] is now 2nd largest
        A[splitPoint] = max;
        unSort(A, lo, splitPoint); // still sorted
        unSort(A, splitPoint + 1, hi); // still sorted
    }
    
    public static int W (int N)
// computes the worst-case running time of MergeSort
    {
        if(N < 2) return 0;
        return (W(N/2)+W((N+1)/2)+N-1);
    }
    
    public static int B (int N)
// computes the best-case running time of MergeSort
    {
        if(N < 2) return 0;
        return (B(N/2)+B((N+1)/2)+N/2);
    }
}