#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdlib>
#include <vector>

using namespace std;

// Слияние упорядоченных частей массива в буфер temp
int Merge(string *array, int left,int middle,int right){
  int compare_count=0;

  int pos_left=left;// текущая позиция чтения из первой последовательности
  int pos_right=middle+1;  // текущая позиция чтения из второй последовательности
  int pos_temp=0;  // текущая позиция записи в temp

  int size = right-left+1; //размер доп.массива
  string *temp = new string[size];

  // идет слияние, пока есть хоть один элемент в каждой последовательности
  while (pos_left <= middle && pos_right <= right) {

    if ( array[pos_left]>array[pos_right] ){
       temp[pos_temp] = array[pos_left];
       pos_temp++;
       pos_left++;

    }else{
      temp[pos_temp] = array[pos_right];
      pos_temp++;
      pos_right++;

    }
    compare_count++;
  }
  // одна последовательность закончилась
  // копировать остаток другой в конец буфера
  while (pos_right <= right){   // пока вторая последовательность непуста
    temp[pos_temp] = array[pos_right];
    pos_temp++;
    pos_right++;
  }

  while (pos_left <= middle){  // пока первая последовательность непуста
    temp[pos_temp] = array[pos_left];
    pos_temp++;
    pos_left++;
    }

  // скопировать буфер temp в array
  for (pos_temp = 0; pos_temp < size; pos_temp++)
    array[left+pos_temp] = temp[pos_temp];

  delete[] temp;

  return compare_count;
}


int NaturalMergeSort(string* array,int start,int end){
    int count=0;

    if(start>=end)
        return 0;

        for(int i=0;i<end-start;i++){
                    int middle = start;
                    int right = start;
                    //ищем первую группу
                    for (middle; middle < end-1; ++middle){
                        count++;
                        if(array[middle] < array[middle+1])
                                break;
                    }

                    if(middle+1==end) //если прошли до конца - то сортирован
                        break;
                    //ищем вторую группу
                    right = middle+1;
                    for (right; right < end-1; ++right){
                        count++;
                        if(array[right]<array[right+1])
                            break;
                    }
                    //сливаем вторую группу
                    count+=Merge(array,start,middle,right);
                    //рекурсивно проходим оставщийся конец
                    count+=NaturalMergeSort(array,right,end);

        }

    return count;

}


void GenerateDataset(const char* filename,int num){
    ofstream out(filename);
    char n3[4]="";

    if(!out){
        cerr<<"File "<<filename<<" not create"<<endl;
        return;
    }

    srand(time(0)*num);//что бы случайнее было

     for(int i=0;i<num;i++){// генерируем и записываем
        n3[0] = (char) (rand()%26+'A');
        n3[1] = (char) (rand()%26+'A');
        n3[2] = (char) (rand()%26+'A');
        out<<n3<<endl;
    }
    out.close();
}

int SortDataset(const char *filename){

    vector<string> temp; //Временно, так как мы не знаем длину файла.

    int size = 0;

    ifstream in(filename); //открываем файл
    int ret = 0;

    if(!in){//ошибка, если не открывается
        cerr<<"File "<<filename<<" not open!"<<endl;
        return -1;
    }
     while(!in.eof()){// загружаем в вектор
        string s;
        in>>s;
        temp.push_back(s);
    }
    in.close();//закрываем

    string *array = &temp[0]; //получаем ссылку из массива vector'а для передачи в метод
    size = temp.size();
    //sorting
    ret = NaturalMergeSort(array,0,size-1);
    //end sorting

    //gen new filename
    string fname(filename);
    fname+=".sort";
    ofstream out(fname.c_str());

    if(!out){
        cerr<<"File "<<fname<<" not open!"<<endl;
        return -1;
    }
    //Записываем сортированный массив
    for(int i=0;i<size;i++)
        out<<array[i]<<endl;

    out.close();
    temp.clear();//ощищаем вектор и память

    return ret;
}
//для логарифма
double Log2( double n )
{
    return log( n ) / log( 2 );
}

const int nums[10] = {8,16,32,64,128,256,512,1024,2048,4096};


int main(){

    ofstream test_table("test_table.txt");
    test_table<<"num\tTe\tT1\tT2\tTe/T1\tTe/T2"<<endl;

    char name[40];
    double Te=0,T1=0,T2=0;

    for(int i=0;i<10;i++){

        sprintf(name,"test/test_%d.txt",nums[i]);
        GenerateDataset(name,nums[i]);

        Te = (double) SortDataset(name);
        T1 = nums[i]*nums[i];
        T2 = round(log2(nums[i])*nums[i]);
        test_table.precision(4);
        test_table<<nums[i]<<"\t"<<Te<<"\t"<<T1<<"\t"<<T2<<"\t"<<Te/T1<<"\t"<<Te/T2<<endl;
    }

    test_table.close();

    return 0;
}