#include <fstream>
#include <queue>
#include <cstdlib>
#define SMALLER runs[aux].buffer[runs[aux].count]

using namespace std;

typedef unsigned long long int ll;

const int numberRuns = 20;
const long long totalSize = (long long)20*(1<<27); //20GB
const long bufferSize = (1<<26); //512MB para cada run
const long runSize = totalSize/numberRuns; //1GB
const int numberBuffers = runSize/bufferSize;
int bufferPlace = 0;
long size;
struct Run {
	ifstream file;
	int buffCount;
	ll buffer[bufferSize];
	bool valid;
	long count;
};

Run runs[numberBuffers];

void loadBuffer (int run) {
	if(runs[run].file.tellg()<totalSize){
		long aux = totalSize - (runs[run].file.tellg() + size);
		if (aux < size) aux = size - aux;
		runs[run].file.read((char*)&runs[run].buffer, (size - aux)*sizeof(ll));
	}
}

int main () {
	bool time = 1;
	ofstream output;
	size=bufferSize;
	while(size<totalSize){
		bufferPlace=0;
		if(time){
			output.open("file2.bin", ios::out | ios::binary);
			for (long i = 0; i < numberBuffers; ++i) {

				runs[i].file.open("file1.bin", ios::in | ios::binary);
				runs[i].file.seekg(((i+bufferPlace)*runSize)*sizeof(ll));
				runs[i].buffCount = 0;
				runs[i].valid = true;
				runs[i].count = 0;
			}
			time = 0;
		}
		else{
			output.open("file1.bin", ios::out | ios::binary);
			for (long i = 0; i < numberBuffers; ++i) {

				runs[i].file.open("file2.bin", ios::in | ios::binary);
				runs[i].file.seekg(((i+bufferPlace)*runSize)*sizeof(ll));
				runs[i].buffCount = 0;
				runs[i].valid = true;
			}
			time = 1;
		}
		for (int i = 0; i < numberBuffers; ++i) {
			loadBuffer(i);
		}
		for (long p = 0; p < totalSize;){
			for (long k = 0; k < (runSize*numberBuffers); ++k, ++p) {
				int aux;
				for(aux = 0; !runs[aux].valid; ++aux);
				printf("teste");
				for (int j = 0; j < numberBuffers; ++j) {
					if (runs[j].valid) {
						if (runs[j].buffer[runs[j].count] < SMALLER) {
							aux = j;
						}
					}
				}
				printf("%d\n", SMALLER);
				output.write((char*)&SMALLER, sizeof(ll));
				++runs[aux].count;
				if (runs[aux].count == bufferSize) {
					if (++runs[aux].buffCount == (numberBuffers)) runs[aux].valid = false;
					if (runs[aux].valid) loadBuffer(aux);
				}
			}
			bufferPlace+=numberBuffers;
			for (int i = 0; i < numberBuffers; ++i) runs[i].file.close();
			output.close();
		}
		size<<=1;
	}
	return 0;
}