Merge Sort program in C

It is rather amazing, that many programmers are unable to write ‘Merge Sort’ correctly. With its guarantee of O(n log n) time complexity, it is a dependable sorting algorithm. Also it can be used to count number of inversions in a array of integers. Most importantly it is very easy to code! :)

So here is my implementation, of merge sort in C language -

/* 
 *We need 2 arrays 'a' and 'b', of equal size
 *Here 'a' is the primary array (i.e which contains initial 
     input, and final output)
 *And 'b' is the temporary array,
     used for merging 2 sorted half's in 'a' 
 */
 
void merge(int a[], int low, int mid, int high)
{
    int b[10000];
    int i = low, j = mid + 1, k = 0;
 
    while (i <= mid && j <= high) {
        if (a[i] <= a[j])
            b[k++] = a[i++];
        else
            b[k++] = a[j++];
    }
    while (i <= mid)
        b[k++] = a[i++];
 
    while (j <= high)
        b[k++] = a[j++];
 
    k--;
    while (k >= 0) {
        a[low + k] = b[k];
        k--;
    }
}
 
void mergesort(int a[], int low, int high)
{
    if (low < high) {
        int m = (high + low)/2;
        mergesort(a, low, m);
        mergesort(a, m + 1, high);
        merge(a, low, m, high);
    }
}
About these ads
This entry was posted in Programming and tagged , , . Bookmark the permalink.

14 Responses to Merge Sort program in C

  1. fahad writes says:

    Are you a experience programmer of C?
    I have some issues. My university old lectures code cannot work on the latest C-++ IDE. I need help. Can you give me ur email address, if u can help me?

    • vinayakgarg says:

      I can guess that your old lectures code contain the “conio.h” stuff, which only works on ancient IDE called “Turbo C++”.
      Whatever your problem, feel free to ask in comments, or even better use the power of Stackoverflow.com

  2. Harsha09 says:

    Readability of the code can be much better,esp with the pre incement operations in the array indices.

  3. Nandini says:

    This is the simplest code,good.

  4. arun says:

    give mergesort algorithm

  5. farmosteast says:

    The result is not right, if you change
    k–;
    while (k >= 0) {
    a[low + k] = b[k];
    k–;

    to
    k–;
    while (k > 0) {
    a[low + k] = b[k];
    k–;

    Then the result is the expected one.

    • farmosteast says:

      Sorry, it is still wrong. Your output array is sorted, but all the elements are right shifted by one element, for example, the input a is 3,1,2, the out put is 0,1,2. “3” is a[3] which is not valid

    • vinayakgarg says:

      Can you please provide sample input where the said implementation fails. I believe you are calling mergesort incorrectly. For N element array, call mergesort(ARRAY, 0, N-1);

  6. subha says:

    this algorithm is easy to understand,good.

  7. thayammal says:

    this algorithm is simple and easy

  8. kutty says:

    easy to learning

  9. engwarrior says:

    How about if you change:
    int b[10000];

    for:

    int *b = malloc(sizeof(int)*(high – low + 1));

    free(b);

  10. sven_kovacic@aol.de says:

    Could you please explain the coding?.. Tried to completely understand this but it´s some kind of difficult for me. It would be awesome if someone could explain this Program line by line to me :)

    • vinayakgarg says:

      If you have written even the simplest recursive functions, understanding merge-sort shouldn’t be a problem. So I suggest you start with recursion. There are plenty of resources on internet. A book would be even better. :)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s