You are asked to modify the textbook version of Merge-Sort on page 31 into a new

Question

You are asked to modify the textbook version of Merge-Sort on page 31 into a new algorithm of Merge-Triplet-Sort. In Merge-Triplet-Sort, an input array A will be split into three equal-sized sub-arrays L, M, and R that stands for left, middle, and right.

a. (10 points) Please revise the textbook pseudocodes of Merge-Sort() and Merge() functions for your Merge-Triplet-Sort algorithm.

b. (10 points) Please find the analytical time complexity of Merge-Triplet-Sort using elimination method. You must show your procedure.

Explanation / Answer

Modified Merge-Sort for  Merge-Triplet-Sort

MERGE (A, p, q, r )

n1 q p + 1

n2 r q

Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]

FOR i 1 TO n1

DO L[i] A[p + i 1]

FOR j 1 TO n2

DO R[j] A[q + j ]

L[n1 + 1]

R[n2 + 1]

i 1

j 1

FOR k p TO r

DO IF L[i ] R[ j]

THEN A[k] L[i]

i i + 1

ELSE A[k] R[j]

j j + 1

MERGE-SORT (A, p, r)

IF p < r // Check for base case

THEN s = FLOOR[(r - p)/3] // Divide it into three subpart

MERGE-SORT (A, p, p+s) //first part   

MERGE-SORT (A, p+s+1, p+2*s) //second part

MERGE-SORT (A, p+2*s+1, q) //third part

MERGE (A, p, p+s, p+2*s) //now merge first and second part, cost is 2*n/3

MERGE (A, p, p+2*s, q) //now merge it with third part, 2n/3 + n/3

T(n) = 3*T(n/3) + n/3 + n/3 + 2n/3 + n/3

T(n) = 3*T(n/3) + (5/3)*n ...........................(1)

T(n/3) = 3*T(n/9) + (5/32)*n ......................(2)

Substituting T(n/3) from eq(2) in eq(1)

T(n) = 3 *( 3*T(n/9) + (5/32)*n ) + (5/3)*n

= 32 * T(n/32) + 2 * (5/3) * n

= 3k * T(n/3k) + k * (5/3) * n

Base Case T(1) = 1

n/3k = 1

k = log3n and n = 3k

T(n) = n + log3n * n * (5/3)

T(n) = O(nlog3n)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.