Implementation of mergesort in C

Question

I have implemented mergesort in C. Any advice on making it more compact? My merge function seems less than fully optimal.

//mergeSort in C

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

void merge(int [], int[], int[], int, int);
void mergesort(int[], int);

int main()
{
    int unsorted[] = {4, 1, 3, 0, 10, 2, 5, 5};
    int size = sizeof(unsorted)/sizeof(int);
    mergesort(unsorted, size);
    printf("The sorted array is: ");
    for(int i = 0; i < size; i++)
    {
        printf("%d, ", *(unsorted+i));
    }

    return 0;
}

void merge(int *original, int* first, int* second, int len1, int len2)
{
    int i = 0; 
    int firPtr = 0; 
    int secPtr = 0;

    while(i < (len1+len2))
    {
        if(firPtr == len1)
        {
            original[i] = second[secPtr++];
        }

        else if(secPtr == len2)
        {
            original[i] = first[firPtr++];
        }

        else if(first[firPtr] < second[secPtr])
        {
            original[i] = first[firPtr++];
        }

        else
        {
            original[i] = second[secPtr++];
        }
        i++;
    }
}
void mergesort(int unsorted[], int size)
{
    if(size <= 1 || unsorted == NULL)
    {
        return;
    }

    int *first = (int *)malloc((size/2)*sizeof(int));
    int *second = (int *)malloc((size - size/2)*sizeof(int));;

    int mid = size/2;

    for(int i = 0; i < mid; i++)
    {
        *(first+i) = *(unsorted+i);
    }

    //Common Error/Note to self: Make sure when initializing j to 
    //not 0, the code block truly requires that.
    for(int j = (mid); j <  size; j++) 
    {
        *(second+(j-mid)) = *(unsorted+j);
    }


    mergesort(first, mid); 
    mergesort(second, size - mid);
    merge(unsorted, first, second, mid, size - mid);
    free(first);
    free(second);
}

Answer 1

Use for loop

This while loop in merge can be easily rewritten as a for loop:

int i = 0; 
// ...

while(i < (len1+len2))
{
    // ...
    i++;
}

The benefit of a for loop is that it limits the scope of the variable i, preventing misuses outside, and it makes the i++ easier to see, impossibly to forget:

for (int i = 0; i < (len1+len2); i++)
{
    // ...
}

Unnecessary recalculation

It's ironic to see size / 2 repeated 2 times, and then again when storing in a variable:

int *first = (int *)malloc((size/2)*sizeof(int));
int *second = (int *)malloc((size - size/2)*sizeof(int));;

int mid = size/2;

You could as well reorder these statements and reuse mid:

int mid = size/2;

int *first = (int *)malloc(mid * sizeof(int));
int *second = (int *)malloc((size - mid) * sizeof(int));

Naming

In merge, the variables firPtr and secPtr are poor names for two reasons:

• "Ptr" suffix is typically used for pointers. But these variables are not pointers, these are indexes. So the suffix should be "Index"
• "fir" and "sec" are meaningless fragments, simply spelling them out to "first" and "second" would make them naturally more readable

Pointer indexing

In some places you use array-style indexing with pointers:

original[i] = first[firPtr++];

... while in many other places you use pointer arithmetics:

printf("%d, ", *(unsorted+i));
// ...
*(first+i) = *(unsorted+i);

I suggest to use simply array-style indexing consistently everywhere.

Usability

As I pointed out on your other questions, the program can become more interesting if it can take input from the command line rather than a hardcoded array. You could rework main easily to that end:

int main(int argc, char ** argv)
{
    int size = argc - 1;
    int * unsorted = (int *)malloc(size * sizeof(int));
    for (int i = 1; i < argc; ++i) {
        unsorted[i - 1] = atoi(argv[i]);
    }

    // ...

    free(unsorted);
}

Minor points

No need for the return 0 at the end of main. The compiler adds that automatically.

The program doesn't print a newline after printing the sorted array. This makes the output look strange when running in a terminal. I suggest to add a newline at the end:

puts("");

Answer 2

Taking memory into consideration:

That code uses \$(n*log(n))\$`sizeof(int)` bytes of heap memory for array elements storage.

This code makes it n `sizeof(int)`. By creating temporary memory only once and passing it to other functions, it saves significant memory in case of large arrays.

/* sorts given input array in ascending order */

void merge_sort (int * arr,int size)
{
    int *temp;
    if((temp = (int*)malloc(sizeof(int)*size))!=NULL)
      msort(arr,temp,0,size-1) ;
}

void msort(int * arr,int * temp,int first,int last)
{
    if (first>= last) return ;

    int split = (first+last) / 2 ;

    msort(arr,temp,first,split) ;
    msort(arr,temp,split+1,last) ;
    merge(arr,temp,first,split,last) ;
}

void merge (int * arr,int *temp,int f_start,int f_end,int s_end)
{
                                /*    s_start == f_end+1      */
    int i = f_start ;
    int j = f_end+1 ;
    int k = f_start ;

    while (i<=f_end && j<=s_end)
    {
        if (arr[i]<arr[j])
            temp[k++] = arr[i++] ;
        else
            temp[k++] = arr[j++] ;
    }

    while (i<=f_end)
            temp[k++] = arr[i++] ;

    while (j<=s_end)
            temp[k++] = arr[j++] ;

    for (i=f_start ; i<=s_end ; i++)
    {
        arr[i] = temp[i] ;
    }
}

Answer 3

When calling malloc():

1. In C, do not cast the returned value. It already has a type of void*, so can be assigned to any pointer.

2. Always check (!=NULL) the returned value from malloc() (and calloc() and realloc()) to assure the operation was successful. If not successful, then a seg fault event will be raised due to accessing memory at address around 0.

Regarding this line:

int *second = (int *)malloc((size - size/2)*sizeof(int));;

There is a second (and unnecessary) ; at the end of the statement.

You could save some CPU cycles by placing the line int mid = size/2; before the calls to malloc() and then using mid in the parameter rather than size/2. Also, a divide is (usually) an expensive operation. I suggest using mid = size>>1;.

Answer 4

You can improve performance of merge a little bit. Also, using more elaborate names for your data won't hurt either. See a possible implementation:

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

void merge(int [], int[], int[], int, int);
void my_mergesort(int[], int); // "my_" because gcc seems to contain "mergesort"

int main()
{
    // Your demo code.
    return 0;
}

void merge(int* original, 
           int* left_array, 
           int* right_array, 
           int left_array_length, 
           int right_array_length)
{
    int i = 0; 
    int left_index = 0; 
    int right_index = 0;

    while (left_index < left_array_length && right_index < right_array_length)
    {
        original[i++] = 
                left_array[left_index] < right_array[right_index] ? 
                    left_array[left_index++] :
                    right_array[right_index++];

    }

    memcpy(original + i, 
           left_array + left_index, 
           (left_array_length - left_index) * sizeof(int));

    memcpy(original + i, 
           right_array + right_index, 
           (right_array_length - right_index) * sizeof(int));
}

void my_mergesort(int unsorted[], int size)
{
    if (size <= 1 || unsorted == NULL)
    {
        return;
    }

    int mid = size / 2;
    int *first  = malloc(mid * sizeof(int));
    int *second = malloc((size - mid) * sizeof(int));;

    memcpy(first, unsorted, mid * sizeof(int));
    memcpy(second, unsorted + mid, (size - mid) * sizeof(int));

    my_mergesort(first, mid); 
    my_mergesort(second, size - mid);
    merge(unsorted, first, second, mid, size - mid);
    free(first);
    free(second);
}