Question

Mergesort uses the divide-and-conquer technique to sort a list. True False

Answer 1

Answer:

True: Merge Sort sorts a list using divide-conquer approach.

Merge_Sort(B,p,n)  //p is the starting index of array B and n is the last index.

1. if(p<n)

2.        q ← (p+n)/2    //divides the list into two sub-lists

2.        Merge_Sort(B, p, q) //sorts the left half

3.        Merge_Sort(B, q+1, n) //sorts the right half.

4.        Merge(B, p, q, n)

Merge(B, p, q, n)

1.l ← q-p+1.  //no. of elements in left half

2.m ← n-q  //no. of elements in right half.

3.for x ← 1 to l

4.      Left[x] = B[p+x -1] //The elements of left half are copied to Left array

5.for y ← 1 to m.

6.      Right[y]= B[q+y]  //The elements of right half are copied to right array

7. x ← 1, y ←1

8.for z ← p to n.

9.      if( Left[x] ≤ Right[y] ) // to merge the two lists Left and Right, the    //elements are compared.

10.     {   A[z] ← Left[x]   //smaller one comes to the merged list.

11.          x++. }

12.    else

13.      {   A[z] ← Right[y]

14.          y++ }

Explanation:

The Merge_Sort(A, p, n) algorithm first divides the whole array into two halves. Then again divides the sub-lists into it's halves and so on.

Then using merge algorithm it compares the elements of both halves one by one and keep it in sorted order.