#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <stdio.h>
#include <iostream>
#include <ctime>
#include <math.h>
#define bittype unsigned __int64
bittype N=15;//Количество строк исходной матрицы
//int L=3;//Количество столбцов исходной матрицы
//bittype BLOCKL=513;//размер блока
//int BLOCKN=513;
//const bool isPrinting=true;//вывод промежуточных и итоговых результатов(при true выводит исходную, результирующую и промежуточные блочные)
//const bool isCreatingMatrix=true;//для создания матрицы где целая часть это число до запятой а столбец число после запятой для проверки
////исходная матрица будет лежать(или стоит положить и сделать поле isCreatingMatrix=false) в бинарном виде в matrix.bin
////транспонированная матрица лежит в бинарном виде в matrixt.bin

void CreateRandom(const char* name)
{
	FILE * pFile;
	pFile = fopen ( name , "wb" );
	fwrite(&N,sizeof(bittype),1,pFile);
	for(int j=0;j<N;j++)
    {

		bittype t=bittype(rand()%100+48);
		bittype i=t;
		if(j==0)
			i=pow(2,59);
        fwrite(&i,sizeof(bittype),1,pFile);

    }
	fclose(pFile
		);
}
const int BLOCK=60000;
int Block;
void merge()
{
	bittype N1,N2,N3;
	FILE *in1;
	in1 = fopen ("in.bin" , "rb" );
	FILE *in2;
	in2 = fopen ( "output.bin" , "rb" );
	FILE *output;
	output = fopen ( "out.bin" , "wb" );
	fread(&N1,sizeof(bittype),1,in1);
	fread(&N2,sizeof(bittype),1,in2);
	N3=N1+N2;
	fwrite(&N3,sizeof(bittype),1,output);
	bittype * Mass1=new bittype[Block];
	bittype * Mass2=new bittype[Block];
	bittype * Mass3=new bittype[Block];
	int i1=0,i2=0,i3=0;
	int result1=0,result2=0;
	bool end1=true,end2=true;
	while(true)
	{
		if((i1==result1) && (end1) )
		{
			result1 = fread(Mass1,sizeof(bittype),Block,in1);
			i1=0;
			if(result1 ==0)
				end1=false;
		}
		if((i2==result2) && (end2))
		{
			result2 = fread(Mass2,sizeof(bittype),Block,in2);
			i2=0;
			if(result2 ==0)
				end2=false;
		}
		if((!end1) && (!end2))
			break;
		if(!end1 || !end2)
		{
		if(end1)
		{
			Mass3[i3]=Mass1[i1];
			i1++;
		}
		if(end2)
		{
			Mass3[i3]=Mass2[i2];
			i2++;
		}
		}
		else
			{
				if(Mass1[i1]<Mass2[i2])
				{
					Mass3[i3]=Mass1[i1];
					i1++;

				}
				else
				{
					Mass3[i3]=Mass2[i2];

					i2++;
				}
			}
		//std::cout<<Mass3[i3]<<" ";
		i3++;
		if(i3==Block)
		{
			fwrite(Mass3,sizeof(bittype),Block,output);
			//std::cout<<"\n";
			i3=0;
		}
	}
	if(i3!=0)
		{
			fwrite(Mass3,sizeof(bittype),i3,output);
		}
	delete Mass1;
	delete Mass2;
	delete Mass3;
	fclose(in1
		);
	fclose(in2
		);
	fclose(output
		);
	remove("in.bin");
	remove("output.bin");
	rename("out.bin","output.bin");
}
void PrinFile(const char* name)
{
	FILE *input;
	bittype L;
	input = fopen ( name , "rb" );
	fread(&L,sizeof(bittype),1,input);
	std::cout<<L<<" :";
	bittype *M=new bittype[L];
	long result=fread(M,sizeof(bittype),L*2,input);
	for(int i=0;i<result;i+=1)
	{
		std::cout<<M[i]<<" ";
	}
	std::cout<<"\n"<<std::endl;
	fclose(input
		);
}
int compare(const void * x1, const void * x2)   // функция сравнения элементов массива
{
	//__int128 t = ( *(bittype*)x1 - *(bittype*)x2 );
  	if(*(bittype*)x1>*(bittype*)x2)
		return 1;
	if(*(bittype*)x1<*(bittype*)x2)
		return -1;
	return 0;             // если результат вычитания равен 0, то числа равны, < 0: x1 < x2; > 0: x1 > x2
}
void Sort()
{
	bittype N1;
	FILE *input;
	input = fopen ( "input.bin" , "rb" );
	FILE *output,*temp;
	output = fopen ( "output.bin" , "wb" );

	fread(&N1,sizeof(bittype),1,input);
	bittype* Mass=new bittype[BLOCK];
	long result=fread(Mass,8,BLOCK,input);
	bittype res=result;
	qsort(Mass, result, sizeof(bittype), compare);
	//for(int i=0;i<result;i+=1)
	//{
	//	std::cout<<Mass[i]<<" ";
	//}
	//std::cout<<"\n";
	fwrite(&res,8,1,output);
	fwrite(Mass,8,result,output);
	fclose(output);
	delete Mass;
	for(int i=0;i<N1;i+=BLOCK)
	{
		Mass=new bittype[BLOCK];
		//fseek(input,i*8+8,SEEK_SET);
		result=fread(Mass,sizeof(bittype),BLOCK,input);
		if(result==0)
			break;
		temp=fopen ( "in.bin" , "wb" );
		res=result;
		qsort(Mass, result, sizeof(bittype), compare);
		fwrite(&res,sizeof(bittype),1,output);
		fwrite(Mass,sizeof(bittype),result,temp);
		fclose(temp);
		delete Mass;
		merge();
	}
	fclose(input);
}
void main()
{
	Block=BLOCK/3;
	//std::cout<< sizeof(bittype);
	//qsort(vector, Block, sizeof(bittype), compare);
	//srand( time( 0 ) );

	//CreateRandom("input.bin");
	//clock_t start=clock();
	//PrinFile("input.bin");
	//clock_t start=clock();
	Sort();

	//std::cout<<(clock()-start)/CLOCKS_PER_SEC<<"\n";
	//PrinFile("output.bin");
	system("pause");
}