#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void merge(int array[], int low, int mid, int high)
{
	int i,j,k;
	int n1=mid-low+1;
	int n2=high-mid;
	int left[n1];
	int right[n2];
	
	for(int i=0; i<n1; i++)
	{
		left[i]=array[low+i];
	}
	
	for(int j=0; j<n2; j++)
	{
		right[j]=array[mid+1+j];
	}
	
	i=0;
	j=0;
	
	k=1;
	
	while(i<n1 && j<n2)
	{
		if(left[i] <= right[j])
		{
			array[k]=left[i];
			i++;
		}
		
		else 
		{
			array[k]=right[j];
			j++;
		}
		k++;
	}
	
	while(i<n1)
	{
		array[k]=left[i];
		i++;
		k++;
	}
	
	while(j<n2)
	{
		array[k]=right[j];
		j++;
		k++;
	}
	
}

void mergesort(int array[], int low, int high)
{
	if(low<high)
	{
		int mid=low+(high-1)/2;
		mergesort(array, low, mid);
		mergesort(array, mid+1, high);
		
		merge(array, low, mid, high);
	}
}

void printarray(int array[], int size)
{
	int i;
	for(i=0; i<size; i++)
	{
		printf("\n%d ", array[i]);
	}
}

int main()
{
	int size;
	FILE *dat;
	dat=fopen("data.txt", "r");
	printf("Enter number of elements\n");
	scanf("%d", &size);
	int array[size];
	for(int i=0; i<size; i++)
	{
		fscanf(dat, "%d", &array[i]);
	}
	printf("Before sort:\n");
	printarray(array,size);
	float t=clock()*1000000;
	mergesort(array, 0, size-1);
	t=(clock()*1000000-t)/CLOCKS_PER_SEC;
	printf("After sort:\n");
	printarray(array, size);
	printf("The time taken is %f microseconds\n", t);
	return 0;
}