Question

Rewrite the MERGE procedure so that it does not use sentinels, instead stopping once either array L or R has had all its elements copied back to A and then copying the remainder of the other array back into A.

Answer 1

Answer:

Merge sort is a sorting technique based on divide and conquer technique.

Explanation:

MERGE(A, p, q, r)

   n1 = q - p + 1

   n2 = r - q

    L[1..n1] and R[1..n2]   this creates the new array

   for i = 1 to n1

       L[i] = A[p + i - 1]

   for j = 1 to n2

       R[j] = A[q + j]

   i = 1

   j = 1

   for k = p to r

       if i > n1

           A[k] = R[j]

           j = j + 1

       else if j > n2

           A[k] = L[i]

           i = i + 1

       else if L[i] ≤ R[j]

           A[k] = L[i]

           i = i + 1

       else

           A[k] = R[j]

           j = j + 1