#include<bits/stdc++.h>
#include <fstream>
#include <sstream>
#include <sys/stat.h>
#include <sys/time.h>
#include <vector>
#include <cstdio>
#include<time.h>
#include<stdio.h>
#define ll long long int

using namespace std;

struct Node
{
	ll data;
	ll  index;
};

class PriorityQueue
{
public:
	int size;
	Node * pq = new Node [1000000];
	PriorityQueue()
	{
		size = 0;
	}

	bool isEmpty()
	{
		return size == 0;
	}

	int getSize()
	{
		return size;
	}
	Node getMin()
	{
		if (isEmpty())
		{
			return {0, 0};
		}
		return pq[0];
	}
	Node top()
	{
		return pq[0];
	}

	void display()
	{
		for (int i = 0; i < size; ++i)
		{
			cout << pq[i].data << " ";
		}
		cout << endl;
	}


	void insert(Node element)
	{
		pq[size] = element;
		size++;
		int childIndex = size - 1;
		while (childIndex > 0)
		{
			int parentIndex = (childIndex - 1) / 2;
			if (pq[childIndex].data < pq[parentIndex].data)
			{
				swap(pq[childIndex] , pq[parentIndex]);
			}
			else
			{
				break;
			}
			childIndex = parentIndex;
		}
	}

	Node  removeMin()
	{
		if (isEmpty())
			return { -1, -1};
		Node min = pq[0];
		pq[0] = pq[size - 1];
		size = size - 1;

		//down-heapify
		int parentIndex = 0;
		int leftChildIndex = 2 * parentIndex + 1;
		int rightChildIndex = 2 * parentIndex + 2;

		while (leftChildIndex <  size)
		{
			int minIndex = parentIndex;
			if (pq[minIndex].data > pq[leftChildIndex].data)
			{
				minIndex = leftChildIndex;
			}
			if (rightChildIndex < size && pq[rightChildIndex].data < pq[minIndex].data)
			{
				minIndex = rightChildIndex;
			}
			if (minIndex == parentIndex)
			{
				break;
			}
			swap(pq[minIndex], pq[parentIndex]);

			parentIndex = minIndex;
			leftChildIndex = 2 * parentIndex + 1;
			rightChildIndex = 2 * parentIndex + 2;
		}
		return min;
	}
};



void chunk_division(string inputFile, string outputFile, vector<string>&store_temp_file_names)
{
	long long int chunk_size = 255; //1000000;
	ll max_num_of_elements = 0;
	cout << "Number of integers in a temporary file : " << chunk_size << endl;

	ifstream in(inputFile);
	ll inp;
	while (!in.eof())
	{
		in >> inp;
		max_num_of_elements++;
	}
	in.close();

	cout << "maximum number of elements :" << max_num_of_elements << endl;

	ll num_of_chunks = max_num_of_elements / chunk_size;
	ll last_chunk_size =  max_num_of_elements % chunk_size;

	if (last_chunk_size != 0)
		num_of_chunks++;
	else
		last_chunk_size = chunk_size;
	cout << "Number of temporary files created : " << num_of_chunks << endl;

	in.open(inputFile);

	for (ll chunk = 0; chunk < num_of_chunks; ++chunk)
	{
		vector<int>data;
		long long int  value;
		for (ll i = 0; i < chunk_size; ++i)
		{
			if (!in.eof()) //until reaches end of file
			{
				in >> value;
				data.push_back(value); //endl lagana padega to get similar to file
			}
		}
		sort(data.begin(), data.end());

		string fileName = "./q2/a/chunk" + to_string(chunk) + ".txt";
		store_temp_file_names.push_back(fileName);

		ofstream out;
		out.open(fileName);

		for (ll x = 0; x < data.size(); x++)
		{
			out << data[x] << endl;
		}
		out.close();
	}
	in.close();


	ofstream out2;
	out2.open(outputFile);

	ifstream file[store_temp_file_names.size()];
	for (int i = 0; i < store_temp_file_names.size(); ++i)
		file[i].open(store_temp_file_names[i]);


	int flag = 1;
	ll value;
	PriorityQueue p;
	for (ll x = 0; x < max_num_of_elements; ++x)
	{
		if (flag == 1)
		{
			for (ll i = 0; i < store_temp_file_names.size(); ++i)
			{
				file[i] >> value;
				ifstream *file1;
				file1 = new ifstream(store_temp_file_names[i].c_str(), std::ios::in);
				p.insert({value , i});
			}
			flag = 0;
		}
		// cout << "before insert\n";
		// p.display();
		if (!p.isEmpty())
		{
			Node ele = p.removeMin();

			out2 << ele.data << endl;
			// cout << "mindata: " << ele.data << endl;

			ll k;
			if (file[ele.index] >> k)
			{
				p.insert({k, ele.index});
				// cout << "chuck" << ele.index << "->  data :" << k << endl;
			}
		}
		// cout << "after insert\n ";
		// p.display();
		// cout << "\n\n";
	}
	for (int i = 0; i < store_temp_file_names.size(); ++i)
		file[i].close();
	out2.close();
}

void delete_temp_chunks(vector<string>store_temp_file_names)
{
	for (int i = 0; i < store_temp_file_names.size(); ++i)
		remove(store_temp_file_names[i].c_str());
}

int main(int argv , char**argc)
{
#ifdef ONLINE_JUDGE
	freeopen("input.txt", "r", stdin);
	freeopen("output.txt", "r", stdin);
#endif
	ll tick1 = clock();

	// if (argv != 3)
	// {
	// 	cout << "wrong cmd , do again like:\n ./a.out ./data/input.txt ./data/output.txt";
	// }



	// string inputFile = "./q2/input.txt" ;
	// string outputFile = "./q2/output.txt" ;


	string inputFile =   argc[1];
	string outputFile =   argc[2] ;



	vector<string>store_temp_file_names;

	chunk_division(inputFile, outputFile, store_temp_file_names );

	delete_temp_chunks(store_temp_file_names);

	ll tick2 = clock();
	ll elapsed = tick2 - tick1;
	double elapsed_time = (double) elapsed / CLOCKS_PER_SEC;
	cout << elapsed_time   << " sec" << endl;
	return 0;
}