# Mergesort in C A cute implementation of mergesort in C

May 18th, 2022

#engineering In preparation for technical interviews, I implemented mergesort in C. The source on Github has an extensive set of tests. I like how ‘cute’ the code looks.

int *MergeSort(int *array, int length)
{
if (NULL == array || length < 1) {
return NULL;
}
return MergeSortRecursive(array, length, 0, length);
}

// right is exclusive, array of [left, right)
int *MergeSortRecursive(int *array, int length, int left, int right)
{
if ((right - left) == 1)
{
int *result = MakeArray(1);
result = array[left];
return result;
}

int middle = (left + right) / 2;

int leftLength = middle - left;
int rightLength = right - middle;

int *leftSide = MergeSortRecursive(array, length, left, middle);
int *rightSide = MergeSortRecursive(array, length, middle, right);

// Now merge the two halfs, k is index into mergedArray
int i = 0, j = 0, k = 0;
int *mergedArray = MakeArray(right - left);

while (i < leftLength && j < rightLength)
{
if (leftSide[i] < rightSide[j])
{
mergedArray[k++] = leftSide[i++];
}
else
{
mergedArray[k++] = rightSide[j++];
}
}

while (i < leftLength)
{
mergedArray[k++] = leftSide[i++];
}

while (j < rightLength)
{
mergedArray[k++] = rightSide[j++];
}

free(leftSide);
free(rightSide);

return mergedArray;
}

int *MakeArray(int length)
{
int *array = malloc(sizeof(int) * length);
// NULL check here?
return array;
}


© Pramod Kotipalli 2022

This site is open source. Improve this page