Divide-and-Conquer A 3-way merge-sort is an algorithm to sort an array A, descri
ID: 641435 • Letter: D
Question
Divide-and-Conquer
A 3-way merge-sort is an algorithm to sort an array A, described as follows:
Divide: divide the array into three (about) equal sized subarrays A[p..q1], A[q1+1..q2] and A[q2+1..r]
Conquer: Recursively sort these three subarrays.
Combine: Call a procedure 3-way-merge(A, p, q1, q2, r) to merge three sorted subarrays to a sorted array (a)
Please write a recursive pseudocode for this algorithm. Assume the 3-way-merge procedure is available to be used (you can call it directly).
3-way-merge-sort(A, p, r) // A: the input array, p: starting index, r: ending index. {
}
(b)(4 points) Please write down the recurrence equation for this 3-way-merge-sort algorithm.
Explanation / Answer
http://ignou.ac.in/userfiles/FINAL_block%202U2_D&C_140213(1).pdf