What is the code for merge sort in c plus plus?

Answer 1

#include <stdio.h>

void merge_sort(int [], int, int);

void merge_array(int [], int, int, int);

main()

{

int a[50], n, i;

printf("\nEnter size of an array: ");

scanf("%d", &n);

printf("\nEnter elements of an array:\n");

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

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

merge_sort(a, 0, n-1);

printf("\n\nAfter sorting:\n");

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

printf("\n%d", a[i]);

getch();

}

void merge_sort(int a[], int beg, int end)

{

int mid;

if (beg < end)

{

mid = (beg+end)/2;

merge_sort(a, beg, mid);

merge_sort(a, mid+1, end);

merge_array(a, beg, mid, end);

}

}www.eazynotes.com Gursharan Singh Tatla Page No. 2

void merge_array(int a[], int beg, int mid, int end)

{

int i, left_end, num, temp, j, k, b[50];

for(i=beg; i<=end; i++)

b[i] = a[i];

i = beg;

j = mid+1;

k = beg;

while ((i<=mid) && (j<=end))

{

if (b[i] <= b[j])

{

a[k] = b[i];

i++; k++;

}

else

{

a[k] = b[j];

j++; k++;

}

}

if (i <= mid)

{

while (i <= mid)

{

a[k] = b[i];

i++; k++;

}

}

else

{

while (j <= end)

{

a[k] = b[j];

j++; k++;

}

}

}

Answer 2

#include<stdio.h>

#include<conio.h>

int j,a[15],i,temp,n;

void main()

{

clrscr();

void createheap(int);

printf("Enter number of elements\n(Not more than 15) ");

scanf("%d",&n);

for(i=1;i<=n;i++)

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

for(i=n;i>=2;i--)

createheap(i);

for(i=n-1;i>=1;i--)

{

temp=a[1];

a[1]=a[i+1];

a[i+1]=temp;

for(j=i;j>=2;j--)

createheap(j);

}

printf("The sorted elements are :\n");

for(i=1;i<=n;i++)

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

getch();

}

void createheap(int y)

{

if(y>1)

{

if(a[y]>a[y/2])

{

temp=a[y];

a[y]=a[y/2];

a[y/2]=temp;

createheap(y/2);

Answer 3

MergeSort uses divide & conquer strategy to sort the elements.

Here, you go on dividing till only one element is left.

Then this element will be merged with the next one and both will be put in correct order and since this is a recursive function, it will be repeated till you complete the merge and come out.

So, here is the sequence of calls:

a[] = {3, 5, 2, 6, 8}

low = 0; high = 4;

mergesort(a, 0, 4)

mid = 0 + 4 / 2 = 2

mergesort(a, 0, 2)

mergesort(a, 3, 4)

merge(a, 0, 4, 2)

Answer:

/* source of code from link above */

mergesort(int a[], int low, int high)

{

int mid;

if(low

{

mid=(low+high)/2;

mergesort(a,low,mid);

mergesort(a,mid+1,high);

merge(a,low,high,mid);

}

return(0);

}

merge(int a[], int low, int high, int mid)

{

int i, j, k, c[50];

i=low;

j=mid+1;

k=low;

while((i<=mid)&&(j<=high))

{

if(a[i]

{

c[k]=a[i];

k++;

i++;

}

else

{

c[k]=a[j];

k++;

j++;

}

}

while(i<=mid)

{

c[k]=a[i];

k++;

i++;

}

while(j<=high)

{

c[k]=a[j];

k++;

j++;

}

for(i=low;i

{

a[i]=c[i];

}

}

Answer

template
void merge_sort(T* a[], size_t size)
{
// Arrays of length 0 or 1 are already sorted.
if( size < 2 )
return;

// Instantiate a new array of the same size as a.
T *b = new T[size];

// Array A initially contains subsets of width 1 element, then 2, 4, 8...
for( size_t width=1; width{
// Dereference a (now known as c).
T *c = *a;

// Array b initially holds subsets of width 2 elements, then 4, 8, 16...
size_t width2 = 2*width;

// Iterate through each pair of subsets in c...

// sub1 is the start index of the first subset of the pair in c.
for( size_t sub1=0; sub1{
// sub2 is the start index of the second subset of the pair in c.
size_t sub2 = min( sub1+width, size );

// next is the start of the next pair of subsets in c.
size_t next = min( sub1+width2, size );

// Start with the first elements in each pair of subsets in c
// (the ones with the lowest values in each subset).
size_t c1 = sub1;
size_t c2 = sub2;

// Iterate through b's elements from index [sub1] to index [next-1].
for( size_t i=sub1; i
// Copy the lowest of the two indexed values in c to b.
b[i] = ( c1=next c[c1]<=c[c2] )) ? c[c1++] : c[c2++];
}

// Swap the roles of *a and b (note that c still points to the dereferenced a at this point).
*a=b; b=c;
}

// Finished with b (*a is now the fully-sorted array).
delete[]b;
}