Question

Write a program to sort the array by using merge using quick sort

Answer 1

void mergesort(int a[],int i,int j);

void merge(int a[],int i1,int j1,int i2,int j2);

 

int main()

{

int a[30],n,i;

printf("Enter no of elements:");

scanf("%d",&n);

printf("Enter array elements:");

 

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

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

 

mergesort(a,0,n-1);

 

printf("\nSorted array is :");

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

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

 

return 0;

}

 

void mergesort(int a[],int i,int j)

{

int mid;

 

if(i<j)

{

 mid=(i+j)/2;

 mergesort(a,i,mid);  //left recursion

 mergesort(a,mid+1,j); //right recursion

 merge(a,i,mid,mid+1,j); //merging of two sorted sub-arrays

}

}

 

void merge(int a[],int i1,int j1,int i2,int j2)

{

int temp[50]; //array used for merging

int i,j,k;

i=i1; //beginning of the first list

j=i2; //beginning of the second list

k=0;

 

while(i<=j1 && j<=j2) //while elements in both lists

{

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

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

 else

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

}

 

while(i<=j1) //copy remaining elements of the first list

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

 

while(j<=j2) //copy remaining elements of the second list

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

 

//Transfer elements from temp[] back to a[]

for(i=i1,j=0;i<=j2;i++,j++)

 a[i]=temp[j];

}