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++];
            b[k++] = a[j++];
    while (i <= mid)
        b[k++] = a[i++];
    while (j <= high)
        b[k++] = a[j++];
    while (k >= 0) {
        a[low + k] = b[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.

15 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

  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
    while (k >= 0) {
    a[low + k] = b[k];

    while (k > 0) {
    a[low + k] = b[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];


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


  10. 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. :)

  11. Anonymous says:

    Beautiful Solution ! very elegant… I have tried to understand merge sort many times, this one just made me learn for life !!

Leave a Reply

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

You are commenting using your 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