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

extern void *mysort(int *p, int size);

#define OVERALLSIZE 256


int main()
{
    int data[OVERALLSIZE], sum;
    extern int add(int *p, int size);
    extern void makerandom(int *p, int size), checksorted(int *p, int size);

    makerandom(data, OVERALLSIZE);
    sum = add(data, OVERALLSIZE);
    mysort(data, OVERALLSIZE);
    if (sum != add(data, OVERALLSIZE))
	printf("total of array changed; sorting must have mangled it\n");
    checksorted(data, OVERALLSIZE);

    return(0);
}


int add(int *p, int size)
{
    int i, sum;
    for (i = sum = 0; i < size; i++)
	sum += p[i];
    return(sum);
}


void makerandom(int *p, int size)
{
    int fd, i;
    if ((fd = open("/dev/urandom", O_RDONLY)) < 0) {
	perror("/dev/urandom");
	exit(1);
    }
    for (i = 0; i < size; i++) {
	unsigned char c;
	if (read(fd, &c, 1) != 1) {
	    /* highly unlikely, so a semi-lousy error message is ok */
	    fprintf(stderr, "unexpected eof or error from reading /dev/urandom\n");
	    exit(1);
	}
	p[i] = c;
    }
    close(fd);
}


void *mysort(int *p, int size)
{
    extern void merge(int *p, int midpoint, int size);

    if (size < 2)
	return(NULL);

    int midpoint = size / 2;
    mysort(p, midpoint);
    mysort(p + midpoint, size - midpoint);
    merge(p, midpoint, size);
    return(NULL);
}


/* merge {from 0 to midpoint} with {from midpoint to size} */
void merge(int *p, int midpoint, int size)
{
    int scratch[size];
    int targ, i = 0, j = midpoint;

    for (targ = 0; targ < size; targ++) {
	if (i == midpoint || (j != size && p[i] > p[j]))
	    scratch[targ] = p[j++];
	else
	    scratch[targ] = p[i++];
    }
    for (i = 0; i < size; i++)
	p[i] = scratch[i];
}


void checksorted(int *p, int size)
{
    int i;
    for (i = 1; i < size; i++) {
	if (p[i] < p[i-1]) {
	    printf("Nope, item %d is %d, which is less than item %d which is %d\n(this is just the first problem; there may be more)\n",
		    i, p[i], i-1, p[i-1]);
	    return;
	}
    }
}