Merge Sort Algorithm With Example Program

10/5/2021

All Articles
#feature of Merge Sort #Merge Sort Algorithm With Example Program #Merge Sort Algorithm

- Merge Sort follows the rule of Divide and Conquer.

But it doesn't divides the list into two halves. - In merge sort the unsorted list is divided into N

sublists, each having one element, because a list of one element is considered sorted. - Then, it repeatedly merge these sublists, to produce new

sorted sublists, and at lasts one sorted list is produced.

Merge Sort is quite fast, and has a time complexity of O(n log n). - It is also a stable sort, which means the "equal" elements are ordered in the same

order in the sorted list.

Lets take a[5] = {32, 40, 68, 3, 8} as the array to be sorted.

void mergesort(int a[], int p, int r)

{

int q;

if(p < r)

{

q = floor( (p+r) / 2);

mergesort(a, p, q);

mergesort(a, q+1, r);

merge(a, p, q, r);

}

}

void merge(int a[], int p, int q, int r)

{

int b[5]; //same size of a[]

int i, j, k;

k = 0;

i = p;

j = q+1;

while(i <= q && j <= r)

{

if(a[i] < a[j])

{

b[k++] = a[i++]; // same as b[k]=a[i]; k++; i++;

}

else

{

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

}

}

while(i <= q)

{

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

}

while(j <= r)

{

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

}

for(i=r; i >= p; i--)

{

a[i] = b[--k]; // copying back the sorted list to a[]

}

}

This Solution is provided by Shubham mishra

This article is contributed by Developer Indian team. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Also folllow our instagram , linkedIn , Facebook , twiter account for more.....