/* From  xxx@xxx.xxx.monash.edu.au  Mon Jun 7  15:08:22  2004
      Below is the good buffer-using merge(), the recursive msort(), and
   the iterative imsort(), as well as a main() that provides a simple test.
      The only issue is that merge() declares a variable size array,
   which is not ANSI C. I can't be bothered changing this as the two
   alternatives are to malloc() and free() every time merge() is called,
   which is slow, or to allocate the buffer space in one of the calling
   functions and pass it in, which makes the code less pretty.
   Cheers, - Joel
*/

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

void merge(int arr[], int p, int n) {      /* used by both sorts */
/* merge arr[0..p-1] and arr[p..n-1] into arr[0..n-1] */
	int i, j, k, buf[p];
	for(i = 0; i < p && arr[i] <= arr[p]; i++)
		;                           /* ! */
	for(j = i; j < p; j++)
		buf[j] = arr[j];
	for(k = i; i < p; k++)
		if(j < n && arr[j] < buf[i])
			arr[k] = arr[j++];  /* ! */
		else
			arr[k] = buf[i++];
}/*merge*/

void msort(int arr[], int n) {             /* recursive merge sort */
	if(n>1) {
		msort(arr, n/2);
		msort(arr+n/2, n-n/2);
		merge(arr, n/2, n);
	}
}/*msort*/

void imsort(int arr[], int n) {            /* iterative merge sort */
	int i, p;
	for(p = 1; p < n; p*=2) {
		for(i = 0; (i+2*p) < n; i += 2*p)
			merge(arr+i, p, 2*p);
		if(p < (n-i))
			merge(arr+i, p, n-i);
	}
}/*imsort*/

int main() {
	int *arr, i, n;
	printf("Size of array to be sorted: ");  /* simple test driver */
	scanf("%d", &n);
	arr = malloc(n*sizeof(int));
	srand(time(NULL));
	for(i = 0; i < n; i++)
		printf("%d ", arr[i] = (float)rand()/RAND_MAX*n);
	putchar('\n');

	imsort(arr, n);                 /* take your */
	/* msort(arr, n); */            /* pick.     */

	for(i = 0; i < n; i++)
		printf("%d ", arr[i]);
	putchar('\n');
	return(0);
}/* CSSE, Monash University, .au, June 2004 */