#include <cstdlib>
#include <ctime>
#include <iostream>

using namespace std;

/** 
   Scala dwa  sąsiednie zakresy tablicy.
   @param a tablica z elementami do scalenia
   @param from początek pierwszego zakresu
   @param mid koniec pierwszego zakresu
   @param to koniec drugiego zakresu
*/
void merge(int a[], int from, int mid, int to)
{  
   int n = to - from + 1; // Rozmiar scalanego zakresu
   // Scal obie połowy do tymczasowej tablicy b.
   // Alokujemy ją dynamicznie, bo jej rozmiar jest znany
   // tylko w czasie wykonywania -- patrz podrozdział 7.4.
   int* b = new int[n];

   int i1 = from;
      // Następny rozpatrywany element z pierwszej połowy
   int i2 = mid + 1;
      // Następny rozpatrywany element z drugiej połowy
   int j = 0; // Następna wolna pozycja tablicy b

   // Dopóki żaden z indeksów i1 i i2 nie przekroczy końca zakresu,
   // przenoś mniejszy z elementów do tablicy b
  
   while (i1 <= mid && i2 <= to)
   {  
      if (a[i1] < a[i2])
      {  
         b[j] = a[i1];
         i1++;
      }
      else
      {  
         b[j] = a[i2];
         i2++;
      }
      j++;
   }

   // Zwróć uwagę, że wykonywana jest tylko jedna z dwu poniższych pętli while.

   // Skopiuj wszystkie pozostałe pozycje z pierwszej połowy.
   while (i1 <= mid)
   {  
      b[j] = a[i1];
      i1++;
      j++;
   }
   // Skopiuj wszystkie pozostałe pozycje z drugiej połowy.
   while (i2 <= to)
   {  
      b[j] = a[i2];
      i2++;
      j++;
   }

   // Skopiuj z powrotem z tablicy tymczasowej.
   for (j = 0; j < n; j++)
   {
      a[from + j] = b[j];
   }

   // Tablica tymczasowa nie jest już potrzebna.
   delete[] b;
}

/**  
   Sortuje elementy zakresu tablicy.
   @param a tablica z elementami do posortowania
   @param from początek sortowanego zakresu
   @param to koniec sortowanego zakresu
*/
void merge_sort(int a[], int from, int to)
{  
   if (from == to) { return; }
   int mid = (from + to) / 2;
   // Sortuj pierwszą i drugą połowę.
   merge_sort(a, from, mid);
   merge_sort(a, mid + 1, to);
   merge(a, from, mid, to);
}

/** 
   Wyświetla wszystkie elementy tablicy.
   @param a tablica do wyświetlenia
   @param size liczba elementów tablicy a
*/
void print(int a[], int size)
{  
   for (int i = 0; i < size; i++)
   {
      cout << a[i] << " ";
   }
   cout << endl;
}

const int MAX_SIZE = 10000000;
int values[MAX_SIZE];

int main()
{  
   srand(time(0));
   cout << "Rozmiar pierwszej tablicy: ";
   int first_size;
   cin >> first_size;
   cout << "Liczba tablic: ";
   int number_of_arrays;
   cin >> number_of_arrays;
   for (int k = 1; k <= number_of_arrays; k++)
   {
      int size = k * first_size;
      double before = time(0);
      const int ITERATIONS = 100;
      for (int i = 1; i <= ITERATIONS; i++)
      {
         for (int i = 0; i < size; i++)
         {
            values[i] = rand() % 100;
         }
         merge_sort(values, 0, size - 1);
      }
      double after = time(0);
      cout << "Rozmiar: " << size << " Czas wykonania: "
         << (after - before) * 1.0 / ITERATIONS
         << " sekund(y)" << endl;
   }
   return 0;
}

