Code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 11
int* mergeSort(int*, int);
int* merge(int*, int, int*, int);
int main(void)
{
int* mergeSorted;
int size;
int indexCounter = 0;
FILE *theFile;
int i,j, count;
//A.dat = 2,000 random integers
//B.dat = 10,000 random integers
//C.dat = 100,000 random integers
//D.dat = 1,000,000 random integers
//E through H.dat are in the same sequence, except they are nearly ordered rather
//than random.
//This is one specific instance of the CPU timing.
//It also writes the numbers to a text file.
//Reads the data file integers into a dynamic array
theFile = fopen("F.dat", "rb");
fread( &size, sizeof(int), 1, theFile);
int* theArray = (int*) malloc((size)*sizeof(int));
for(i=0;i<size;i++)
fread( &(theArray[i]), sizeof(int), 1, theFile);
fclose(theFile);
unsigned long finish = 0L, start = 0L;
//clocking the merge sort function
start = clock();
mergeSorted = mergeSort(theArray,size);
finish = clock() - start;
finish = finish / (CLOCKS_PER_SEC / 1000);
//writing the sorted array to a text file
FILE *aText;
aText = fopen("fText.txt","w");
fprintf(aText,"10000 random integers sorted:\n");
for(i=0;i<1000;i++)
{
fprintf(aText,"\nRow %6d: ",indexCounter);
for(j=0;j<10;j++)
{
fprintf(aText,"%6d ",mergeSorted[indexCounter]);
indexCounter++;
}
}
//Lastly print the sorting CPU time elapsed to the screen
printf("Time to sort F.dat: %lu milliseconds\n", finish);
//If needed
//system("Pause");
return 0;
}
//Function Calls
//Merge Sort function
int* mergeSort(int* theArray,int size)
{
int i;
//If the partition size is 1, we're done subdividing so return recursively
if (size<=1)
{
//////////////// printf("partition is now size 1, returning\n");
return theArray;
}
else
{
int* left;
int* right;
int middle;
int leftSize;
int rightSize;
int counter;
middle = (size / 2) + 1;
//////////////// printf("Size:%d\n",size);
//////////////// printf("middle size: %d\n",middle);
//dynamically allocating space for the left half of the partition
left = (int*) malloc((middle-1)*sizeof(int));
leftSize=(middle-1);
//////////////// printf("Left Size:%d\n",leftSize);
//If size of subArray is odd, we have to make some adjustments
//in how we handle the right half of the partition
if(size%2==1)
{
//dynamically allocating the space for the right half of the partition
right = (int*) malloc((middle)*sizeof(int));
rightSize=middle;
}
//Else if size of subArray is even, proceed this way
else
{
right = (int*) malloc((middle-1)*sizeof(int));
rightSize=(middle-1);
}
///////////////// printf("Right Size:%d\n",rightSize);
//Copying the left half of the partition to the array left[]
for(i=0;i<(middle-1);i++)
{
left[i] = theArray[i];
///////////////// printf("left%d\n",left[i]);
}
//again we have to handle odd right half slightly different
if(size%2==1)
{
counter=0;
//Copying the right half of the partition to the array right[]
for(i=(middle-1);i<size;i++)
{
right[counter] = theArray[i];
///////////////// printf("right%d\n",right[counter]);
counter++;
}
}
else
{
counter = 0;
for(i=(middle-1);i<size;i++)
{
right[counter] = theArray[i];
///////////////// printf("right%d\n",right[counter]);
counter++;
}
}
///////////////// system("Pause");
//split the left side up until it is in size 1 subarrays
left = mergeSort(left,leftSize);
//split the right side up until it is in size 1 subarrays
right = mergeSort(right,rightSize);
int* merged;
//merge left and right recursively
merged = merge(left, leftSize, right, rightSize);
return merged;
}
}
//Merge Function
int* merge(int* left, int leftSize, int* right, int rightSize)
{
int leftSizeCopy,rightSizeCopy;
///////////////// printf("Merge function called. Left Size: %d, Right Size: %d\n",leftSize,rightSize);
leftSizeCopy = leftSize;
rightSizeCopy = rightSize;
int counter = 0;
int i;
int* result = (int*) malloc ((leftSize+rightSize)*sizeof(int));
//while there are unsorted numbers left
while ( (leftSize > 0) || (rightSize > 0) )
{
int* holder;
//if both sides have unsorted numbers in them
if( (leftSize > 0) && (rightSize > 0) )
{
//compare the first cell on the left with first on the right
//if it's less
if(left[0]<=right[0])
{
//copy the number into a sorted array
//and copy all of the left side minus the copied number into a new malloc
//then point left at the new malloc pointer
result[counter] = left[0];
counter++;
leftSize--;
if(leftSize!=0)
{
holder = (int*) malloc((leftSize)*sizeof(int));
for(i=1;i<=leftSize;i++)
{
holder[i-1] = left[i];
}
left = holder;
}
}
//else, if the right side's first cell is greater than that of the left side
else if(right[0]<left[0])
{
//copy the number into the sorted array
//and copy all of the right side minus the copied number into a new malloc
//then point right at the new malloc pointer
result[counter] = right[0];
counter++;
rightSize--;
if(rightSize!=0)
{
holder = (int*) malloc((rightSize)*sizeof(int));
for(i=1;i<=rightSize;i++)
{
holder[i-1] = right[i];
}
right = holder;
}
}
}
else if(leftSize > 0)
//if the left size is greater than 0 but the right side is emptied out
//copy the cells over to the sorted array
//and reduce the size of left as before using malloc
{
result[counter] = left[0];
counter++;
leftSize--;
if(leftSize!=0)
{
holder = (int*) malloc((leftSize)*sizeof(int));
for(i=1;i<=leftSize;i++)
{
holder[i-1] = left[i];
}
left = holder;
}
}
else if(rightSize > 0)
{
//if the right size is greater than 0 but the left side is emptied out
//copy the cells over to the sorted array
//and reduce the size of right as before using malloc
result[counter] = right[0];
counter++;
rightSize--;
if(rightSize!=0)
{
holder = (int*) malloc((rightSize)*sizeof(int));
for(i=1;i<=rightSize;i++)
{
holder[i-1] = right[i];
}
right = holder;
}
}
}
return result;
}