//
// Author:  SUZUKI, RICARDO

// Merge sort program
// last update on Saturday, April 26

#include<iostream>
#include<cstdlib>
#include<fstream>
#include<iomanip>

using namespace std;

int Many_int();
//PRECONDITION: there must be a .txt file with int
//POSTCONDITIN: returns the amount of int in the file

void fill_up_array(int array[]);
//PRECONDITION: receives an array
//POSTCONDITIN: fill it up with the numbers from
//			the .txt file

void mergesort(int array[], int size);
//PRECONDITION: receives the array and its size
//POSTCONDITIN: sorts the array

void print(int array[], int size);
//PRECONDITION: receives the array and its size
//POSTCONDITIN: print the array

void main()
{
	int dummy=0;
	int	many_numbers = Many_int();
	
	int *array_to_merge;
	array_to_merge = new int[many_numbers];
	
	fill_up_array(array_to_merge);
			
	// call the sort function
	mergesort(array_to_merge, many_numbers);

	print(array_to_merge, many_numbers);

}
void print(int array[], int size)
{
	ofstream outfile;
	outfile.open("output.txt");

	outfile<<" Merge Sort"<<endl;
	for( int i=0; i< size ; i++)
	{
		outfile<<setw(10)<<array[i]<<endl;
	}
	outfile.close();
	
}

//*************** M E R G E   S O R T*****************
void mergesort(int array[], int many_int)
{
	long *aux;
	aux = new long[many_int];

	int i,j,k,L1,L2,size,U1,U2;
	size = 1; 
	while (size <many_int)
	{
		L1 = 0;
		k = 0;
		while (L1+size < many_int)
		{ 
			L2 = L1 + size;
			U1 = L2 - 1;
			U2 = (L2+size-1 < many_int) ? L2+size-1 : many_int-1;
			for (i=L1, j=L2; i<=U1 && j<=U2; k++)
				if (array[i] <= array[j])
					aux[k] = array[i++];
				else
					aux[k] = array[j++];
				for (; i<=U1;k++)
					aux[k] = array[i++];
				for (; j <=U2;k++)
					aux[k] = array[j++];
				L1 = U2 + 1;
		} 
		for (i = L1; k<many_int; i++)
			aux[k++] = array[i];
		for (i=0; i<many_int;i++)
			array[i] = aux[i];
		size *=2;
	}
}



// get integers from file and put in array
void fill_up_array(int array[])
{
	int dummy;
	int i=0;
	ifstream fill_array;
	fill_array.open("input.txt");
	
	while(!fill_array.eof())
	{	
		fill_array>>dummy;
		array[i] = dummy;
		i++;
	}	
	fill_array.close();	
}

// counts how many numbers in the file
int Many_int()
{
	ifstream count_file;
	count_file.open("input.txt");
	if(!count_file)
	{
		cout<<"There is no file to read"<<endl;
		return EXIT_FAILURE;
	}
	
	int many_numbers=0;
	int dummy;
	
	while(!count_file.eof())
	{
		count_file>>dummy;
		many_numbers++;	
	}
	--many_numbers;
	count_file.close();
	return many_numbers;
}