#include <stdio.h>

#include <stdlib.h>



void merge(int *dst, int *src, int left, int middle, int right)

{

	int i,j,k;



	k = left;

	i = left;

	j = middle+1;

	while( i<=middle && j<=right ){

		if(src[i] < src[j]){

			dst[k++] = src[i++];

		}else{

			dst[k++] = src[j++];

		}

	}



	if(j<=right){

		while(j<=right){

			dst[k++] = src[j++];

		}

	}else{

		while(i<=middle){

			dst[k++] = src[i++];

		}

	}

}



void mSort(int *dst, int *src, int left, int right)

{

	int i;

	if(left == right){

		dst[left] = src[right];

	}else{

		mSort(dst, src, left, (left+right)/2);

		mSort(dst, src, (left+right)/2+1, right);

		merge(src, dst, left, (left+right)/2, right);

		for(i=left; i<=right; i++){

			dst[i] = src[i];

		}

	}

}



void mergeSort(int *seq, int len)

{

	int dst[100];

	mSort(dst, seq, 0, len-1);

}

					

void main()

{

	int ancient[] = {49,38,65,97,76,13,27,49};

	int seq[] = {49,38,65,97,76,13,27,49};

	int n = sizeof(seq)/sizeof(int);

	int i;



	printf("Simple selection sort: \n");

	printf("Seq:\n");

	for (i=0; i<n; i++) {

		seq[i] = ancient[i];

		printf(" %2d", seq[i]);

	}	

	printf("\n");

	mergeSort(seq, n);

	for (i=0; i<n; i++) {

		printf(" %2d", seq[i]);

	}	

	printf("\n");



}