#include <iostream.h>
#include <stdlib.h>

// program sortujacy zadany wektor liczb calkowitych wg. algorytmu MergeSort

// Algorytm MergeSort:
//1. Podziel tablice na 2 rowne czesci
//2. Posortuj kazda czesc alg. MergeSort
//3. Scal posortowane czesci do wektora uporzadkowanego.

//czas dzialania O(n log n)



void mergesort(int*,int);
void scalaj(int*,int,int*,int,int*);
void kopiuj(int*,int*,int);

int main(){
  int *T,N;
  int i;

  cout << "Ile liczb zamierzasz wprowadzic ? :";
  cin >> N;

  T=new int[N];
  if ( !T ){
    cerr << "Blad alokacji!" << endl;
    exit(1);
  }

  for ( i=0 ; i<N ; i++ ){
    cout << " Podaj liczbe " << i+1 << " : ";
    cin >> T[i];
  }

  mergesort(T,N);

  cout << "Posortowany wektor:\n";

  for ( i=0 ; i<N ; i++ )
    cout << T[i] << ",";
  cout << endl;

  delete [] T;

  return 0;
}

void mergesort(int *T,int size){
  int rozm1=size/2,rozm2=size-rozm1;
  int *Pom;	// tablica pomocnicza

  //jesli jest to tablica 1-elementowa, to juz jest posortowana
  if ( size==1 )
    return;

  // posortuj poczatkowe size/2 elementow
  mergesort(T,rozm1);

  // posortuj pozostala czesc tablicy
  mergesort(T+rozm1,rozm2);

  // alokacja pomocniczej tablicy
  Pom=new int[size];
  if ( !Pom ){
    cerr << "Blad alokacji!" <<endl;
    exit(1);
  }

  // scalenie posortowanych fragmentow tablicy do tablicy Pom
  scalaj(T,rozm1,T+rozm1,rozm2,Pom);

  // skopiowanie tablicy Pom do tablicy ktora sortujemy
  kopiuj(T,Pom,size);

  // zwolnienie pamieci Pom
  delete [] Pom;

}


// funkcja wykonujaca scalanie 2 tablic posortowanych source1 i source2
// do tablicy target
void scalaj(int *source1,int rozm1,int *source2,int rozm2,int *target){
  while ( rozm1+rozm2>0 )
    // zbadanie z ktorej tablicy trzeba brac kolejny element
    if ( (rozm1!=0 && *source1 < *source2) || rozm2==0 ){
      *(target++)=*(source1++);
      rozm1--;
    }
    else {
      *(target++)=(*source2++);
      rozm2--;
    }
}

// funkcja kopiujaca tablice source do target
void kopiuj(int* target,int *source,int rozmiar){
  while ( rozmiar-->0 )
    *(target++)=*(source++);
}