a-non-recursive-implementation-of-merge-sort.c

#include <stdio.h>
#include <math.h>
int main(int argc, char const *argv[])
{
	long long int array[10000],n,/*array size*/lon,i;
	long long int output[10000],j,k,low,high,mid,l,m,lowi,highi,midi;
	scanf("%lld", &n);
	lon=log2(n);
	for (i = 0; i < n; ++i)
	{
		scanf("%lld", &array[i]);
	}
	for (i = 1; i <= lon; ++i)
	{
		for (j = 1; j <= n; j+=pow(2,i))
		{
			low=j-1;
			high=j+pow(2,i)-1;
			mid=(low+high)/2;

			lowi=j-1;
			highi=j+pow(2,i)-1;
			midi=(low+high)/2;
			k=0;
			while(lowi<mid && midi<high)
			{
				if (array[lowi]<=array[midi])
				{
					output[k++] = array[lowi++];
				}
				else
					output[k++]=array[midi++];
			}
			while(lowi<mid)
				output[k++]=array[lowi++];
			while(midi<high)
				output[k++]=array[midi++];
			k--;
			while(k>=0)
			{
				array[low + k] = output[k];
        		k--;
			}
		}
	}
	for (i = 0; i < n; ++i)
	{
		printf("%lld ", array[i]);
	}
	return 0;
}
/*
			while (l <= mid && m <= high)
		    {
		        if (array[l] <= array[m])
		            output[k++] = array[l++];
		        else
		            output[k++] = array[m++];
		    }
		    while (l <= mid)
		        output[k++] = array[l++];
		    while (m <= high)
		        output[k++] = array[m++];
*/