#include <iostream>
#include <ctime>
#include <cstdio>
#include <windows.h>
#include <algorithm>


#define SIZE (1<<22)
#define MAX_RAND 10

void sort(int []);
void merge(int [],int, int, int);
void tiledmergesort( int [] , int , int );
double timeMERGESORT( int [] );



int main()
{
    srand(time(NULL));
    long long int i;
    int* data = new int[SIZE];
    int* data_copy = new int[SIZE];

    for ( i = 0 ; i < SIZE ; ++i )
    {
        data[i] = rand() % MAX_RAND;
        data_copy[i] = data[i];
    }

    //std::cout<<"insertion sort : "<<timeINSERTION( data )<<std::endl;

    for ( i = 0 ; i < SIZE ; ++i )
    {
        data[i] = data_copy[i];
    }





    std::cout<<"mergesort      : "<<timeMERGESORT( data )<<std::endl;

    return 0;
}





double timeMERGESORT( int array[] )
{
    LARGE_INTEGER ticksPerSecond;
    LARGE_INTEGER tick1;
    LARGE_INTEGER tick2;

    LARGE_INTEGER time1;
    LARGE_INTEGER time2;

    QueryPerformanceFrequency(&ticksPerSecond);
    QueryPerformanceCounter(&tick1);

    double start = double(tick1.QuadPart)/ticksPerSecond.QuadPart;

    sort( array );

    QueryPerformanceCounter(&tick2);

    double end = double(tick2.QuadPart)/ticksPerSecond.QuadPart;
    double diff = end - start;

    return (diff);
}

void sort( int array[] )
{
    int width;

    for ( width = 1; width < SIZE; width = 2*width )
    {
    // Combine pairs of array a of width "width"
        int i;

        for ( i = 0; i < SIZE; i = i + 2*width )
        {
            int left, middle, right;

            left = i;
            middle = i + width;
            right  = i + 2*width;

            merge( array, left, middle, right );

        }
    }
}

void merge(int a[] , int iLeft , int iMiddle, int iRight )
   {
      int i, j, k;
      int* tmp = new int[SIZE];

      i = iLeft;     // Re-adjust the indices
      j = iMiddle;
      k = iLeft;

      while ( i < iMiddle || j < iRight )    // It's the same algorithm !
      {
         if ( i < iMiddle && j < iRight )
         {  // Both array have elements
            if ( a[i] < a[j] )
               tmp[k++] = a[i++];
            else
               tmp[k++] = a[j++];
         }
         else if ( i == iMiddle )
            tmp[k++] = a[j++];      // a is empty
         else if ( j == iRight )
            tmp[k++] = a[i++];      // b is empty
      }

      /* =================================
         Copy tmp[] back to a[]
         ================================= */
      for ( i = iLeft; i < iRight; i++ )
         a[i] = tmp[i];

    delete[] tmp;
}