gistfile1.c

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

// simple merge sort with 2n space requirement

#define N 20
#define A {2, 18, 4, 20, 13, 11, 14, 9, 17, 15, 3, 12, 7, 1, 8, 6, 19, 5, 10, 16}

int merge(int*, int);
void smerge(int*, int, int*);

int main(void) {
	int arr[N] = A;
	merge(arr, N);
	
	int i;
	for (i = 0; i < N; i++)
	{
		printf("%d\n", arr[i]);
	}
	return 0;
}

int merge(int *C, int n)
{
	int * S = malloc (n * sizeof(int));
	if (!S)
	{
		return 1;
	}
	memcpy (S, C, n * sizeof(int));
	smerge(C, n, S);
	free(S);
	return 0;
}

void smerge(int *C, int n, int * S){
	if (n > 1)
	{	
		int na = n/2;
		int nb = (n/2) + (n%2);
		
		smerge(C, na, S);
		smerge(C + na, nb, S);
		
		int i = 0;
		int j = na;
		int k = 0;
		
		while (1)
		{
			if (C[i] < C[j])
			{
				S[k++] = C[i++];
				if (i == na)
				{
					memcpy (S + k, C + j, (n - k) * sizeof(int));
					break;
				}
				
			}
			else
			{
				S[k++] = C[j++];
				if (j == n)
				{
					memcpy (S + k, C + i, (na - i) * sizeof(int));
					break;
				}
			}
		}
		memcpy (C, S, n * sizeof(int));
		
	}
}