HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

Implementation of mergesort in C

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
implementationmergesortstackoverflow

Problem

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 
#include 

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);
}

Solution

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] ;
    }
}

Code Snippets

/* 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] ;
    }
}

Context

StackExchange Code Review Q#115976, answer score: 2

Revisions (0)

No revisions yet.