Answer:
True: Merge Sort sorts a list using divide-conquer approach.
<u>Merge_Sort(B,p,n)</u> //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)
<u>Merge(B, p, q, n)</u>
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.
