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

#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define MAXSIZE 20

typedef int Status;
typedef int KeyType;
typedef int InfoType;
typedef struct {
	KeyType key;
	InfoType otherinfo;
}RcdType;
typedef struct {
	RcdType r[MAXSIZE+1];
	int length;
}SqList;

void ListInsert(SqList *L)
{
	int i, n;
	
	printf("Input number of key: ");
	scanf("%d", &n);
	if(n>MAXSIZE)
		exit(ERROR);

	L->r[0].key = 0;
	L->length = 0;
	for(i=1; i<=n; i++)
	{
		printf("Input key: ");
		scanf("%d", &L->r[i]);
		L->length++;
	}
}

void ListTraverse(SqList L)
{
	int i;
	for(i=1; i<=L.length; i++)
		printf("%d ", L.r[i].key);
	printf("\n");
}

Status LQ(KeyType m, KeyType n)
{
	if(m <= n)
		return TURE;
	else
		return FALSE;
}

void Merge(RcdType SR[], RcdType TR[], int i, int m, int n)
{
	int j, k;
	for(j=m+1, k=i; i<=m && j<=n; k++)
	{
		if(LQ(SR[i].key, SR[j].key))
			TR[k] = SR[i++];
		else
			TR[k] = SR[j++];
	}
	while(i<=m)
		TR[k++] = SR[i++];
	while(j<=n)
		TR[k++] = SR[j++];
}

void MSort(RcdType SR[], RcdType TR1[], int s, int t)
{
	int m;
	RcdType TR2[s+t];

	if(s==t)
		TR1[s] = SR[s];
	else
	{
		m = (s+t)/2;
		MSort(SR, TR2, s, m);
		MSort(SR, TR2, m+1, t);
		Merge(TR2, TR1, s, m, t);
	}
}

void MergeSort(SqList *L)
{
	MSort(L->r, L->r, 1, L->length);
}

void MergePass(RcdType SR[], RcdType TR[], int l, int n)
{
	int i;
	for(i=1; i+2*l-1<=n; i+=2*l)
		Merge(SR, TR, i, i+l-1, i+2*l-1);
	if(i+l-1 < n)
		Merge(SR, TR, i, i+l-1, n);
	else
		while(i <= n)
		{
			TR[i] = SR[i];
			i++;
		}
}

void MergeSortNR(SqList *L)
{
	int l, n=L->length;
	RcdType TR[n+1];

	for(l=1; l<n; l*=2)
	{
		MergePass(L->r, TR, l, n);
		l *= 2;
		MergePass(TR, L->r, l, n);
	}
}

void main()
{
	SqList L;
	
	ListInsert(&L);
	MergeSort(&L);
	ListTraverse(L);

	ListInsert(&L);
	MergeSortNR(&L);
	ListTraverse(L);
}