4
\$\begingroup\$

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);
}
\$\endgroup\$

4 Answers 4

1
\$\begingroup\$

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("");
\$\endgroup\$
5
  • 1
    \$\begingroup\$ i often get the suggestion to rewrite a while loop as a for loop and vice versa. What is the benefit of doing either one? \$\endgroup\$
    – user85591
    Jan 6, 2016 at 8:52
  • \$\begingroup\$ Hello, actually I am very conscious about your usability portion of the answer. I just didn't know how to take in an array as an argument, and figured it would be troublesome to do so, given the main purpose of the program was to just do mergesort. However, thank you for your example on how to take in an array from the command line. \$\endgroup\$
    – user85591
    Jan 6, 2016 at 8:54
  • \$\begingroup\$ Lastly, I looked at the documentation for puts();. Looks so short and simple, why use printf in that case? Esp since puts appends a newline character for you also. \$\endgroup\$
    – user85591
    Jan 6, 2016 at 8:56
  • 1
    \$\begingroup\$ I explained the benefits of the for loop in the first section above. Use a for loop when a single incrementing/decrementing variable controls the loop, typically when iterating over elements of an array, or when counting to a target. Otherwise use another kind of loop. To learn much more, I recommend Code Complete's Chapter 16: Controlling Loops \$\endgroup\$
    – janos
    Jan 6, 2016 at 9:07
  • 1
    \$\begingroup\$ As you mention, puts is simple, and that's both its power and limitation. It's fast because it's simple, but if you need to print something without a trailing newline, or use formatting, then you cannot use it, as it simply doesn't support these features. \$\endgroup\$
    – janos
    Jan 6, 2016 at 9:08
2
\$\begingroup\$

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] ;
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ Welcome to Code Review! Good job on your first post \$\endgroup\$
    – SirPython
    Feb 11, 2016 at 21:32
  • \$\begingroup\$ You are missing a free()... \$\endgroup\$ May 22, 2017 at 21:57
1
\$\begingroup\$

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;.

\$\endgroup\$
3
  • \$\begingroup\$ However, if I don't cast return value for malloc, it gives me warning. (But yes, I am aware that it has return type void*) \$\endgroup\$
    – user85591
    Jan 7, 2016 at 12:49
  • \$\begingroup\$ But thanks for that bit shift reminder. I totally forgot that division is a pretty expensive operation. :) \$\endgroup\$
    – user85591
    Jan 7, 2016 at 12:50
  • \$\begingroup\$ @JonathanSmit, What compiler and what parameters are you using to compile? On my computer, running ubuntu linux 14.04 and using gcc -c -Wall -Wextra -Wconversion -std=c99 no warning is raised when the returned value from malloc() is not cast \$\endgroup\$ Jan 7, 2016 at 14:14
0
\$\begingroup\$

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);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.