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

### Like this:

Like Loading...

*Related*

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?

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

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

This is the simplest code,good.

give mergesort algorithm

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.

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

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

this algorithm is easy to understand,good.

this algorithm is simple and easy

easy to learning

How about if you change:

int b[10000];

for:

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

…

free(b);

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

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