#include <stdio.h>

void mergesort(int* array, int length);
void merge(int* array, int* left, int leftlen, int* right, int rightlen);

// This is a recursive divide-and-conquer sorting algorithm known to programmers
// around the world as Mergesort
// array - The integers to be sorted
// length - The length of that array
void mergesort(int* array, int length)
{
	int* lefthalf;
	int* righthalf;
	int i;

    // Base case: An array with one or zero elements is already trivially sorted
	if(length <= 1)
	{
		return;
	}

    // Copy off the left half of the array and recursively mergesort it
	lefthalf = (int*)calloc(length/2, sizeof(int));
	for(i = 0; i < length/2; i++)
	{
		lefthalf[i] = array[i];
	}
	mergesort(lefthalf, length/2);

    // Copy off the right half of the array and recursively mergesort it
	righthalf = (int*)calloc(length - length/2, sizeof(int));
	for(i = length/2; i<length; i++)
	{
		righthalf[i - length/2] = array[i];
	}
	mergesort(righthalf, length - length/2);

    // Merge the two sorted halves of the array into one
	merge(array, lefthalf, length/2, righthalf, length-length/2);

    // Free up the memory you used to store the two halves of the array
    // You'd have a MASSIVE memory leak otherwise
	free(lefthalf);
	free(righthalf);
}

// Merges two already sorted arrays into one
// array - The array to merge the two smaller arrays into
// left - One of the sorted arrays
// leftlen - The number of integers in left
// right - The other sorted array
// rightlen - The number of integers in right
void merge(int* array, int* left, int leftlen, int* right, int rightlen)
{
	int arrayindex = 0;
	int leftindex = 0;
	int rightindex = 0;

    // As long as both arrays have more integers, keep merging
	while(leftindex < leftlen && rightindex < rightlen)
	{
        // If the smallest remaining integer in the left half is smaller than
        // the smallest remaining integer in the right half, put the integer 
        // from the left half into the final array first
		if(left[leftindex] <= right[rightindex])
		{
			array[arrayindex] = left[leftindex];
			arrayindex++;
			leftindex++;
		}
		// Otherwise, go with the right half
		else
		{
			array[arrayindex] = right[rightindex];
			arrayindex++;
			rightindex++;
		}
	}

    // If there aren't any integers left in the right half, that means there
    // must still be some in the left half. Copy the remaining integers from the
    // left half of the array.
	if(rightindex >= rightlen) 
	{
		while(leftindex < leftlen)
		{
			array[arrayindex] = left[leftindex];
			arrayindex++;
			leftindex++;
		}
	}
	// Otherwise, there are still integers in the right half, so copy those
	else
	{
		while(rightindex < rightlen)
		{
			array[arrayindex] = right[rightindex];
			arrayindex++;
			rightindex++;
		}
	}
}

int main(void)
{
	int array[] = {3, 5, 2, 4, 1, 7, 6, 9, 8};
	int i=0;

    // Output the array before it's sorted
	for(i=0;i<9;i++)
		printf("%d ",array[i]);
	printf("\n");

    // Sort the array
	mergesort(array, 9);

    // Output the array after it's sorted
	for(i=0;i<9;i++)
		printf("%d ",array[i]);
	printf("\n");
	
	system("PAUSE");
}