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 an 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. 🙂

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

not correct. the middle index, m should not be computed as m=(left+right)/2, it should be m = left+(left+right)/2.

sorry, it’s correct!

at a first glance i thought you do m=(right-left)/2 and i wanted to say m = left+(right-left)/2 but then i watched closely and i saw that you compute m=(right+left)/2

Where is the main function ??

I didn’t add main function as I wanted to focus only on the sorting routine in the posted program. It should be rather easy to write it on your own.

Can you right it with the main function, I’m kinda new at this stuff, please.

lots of problem this program gives the linking error

The program is just a fragment of entire code. I aimed it towards intermediate programmers who can at least resolve linker errors.

#include

void main()

{

int A[10],B[10],C[20];

int i, j,k;

int n1,n2,n3;

printf(” Enter the number of elements in A[] \n”);

scanf(“%d”, &n1);

printf(” Enter the Array elements of A[] in sorted form \n”);

for (i = 0; i < n1; i++)

scanf("%d", &A[i]);

printf(" A[] Entered is \n");

for (i = 0; i < n1; i++)

printf(" %d", A[i]);

printf("\n Enter the number of elements of B[] \n");

scanf("%d", &n2);

printf(" Enter the Array elements of B[] in sorted form\n");

for (i = 0; i < n2; i++)

scanf("%d", &B[i]);

printf(" B[] Entered is \n");

for (i = 0; i < n2; i++)

printf(" %d", B[i]);

i=0;j=0;

k=0;

while (i<n1 && j<n2)

{

if (A[i]<=B[j])

{

C[k]=A[i];

i++;

}

else

{

C[k]=B[j];

j++;

}

k++;

}

while (i<n1)

{

C[k]=A[i];

i++;

k++;

}

while (j<n2)

{

C[k]=B[j];

j++;

k++;

}

n3=n1+n2;

printf("\n New Array is…\n");

for (i = 0; i < n3; i++)

printf(" %d",C[i]);

}

Can u explain this part,specially the (k–)on both place..

while (i <= mid)

b[k++] = a[i++];

while (j = 0) {

a[low + k] = b[k];

k–;

Nice one

Don’t you think it’ll be better to create a array of b[high-low+1] rather than creating and array of b[10000] in the merge function ?