In the lesson on Merge Sort, we implemented merge sort where we divided the array into two parts at each recursion step. Imagine you are asked to implement merge sort by dividing the problem into three parts instead of two. You can assume for simplicity that the input size will always be a multiple of 3. Use a priority queue to merge sub-arrays in the combining step.a- Provide implementation for the 3-way division merge sort.b- Provide a generalized expression for the number of recursion levels.c- Work out the time complexity for the 3-way merge sort.d- Will implementing merge sort by dividing the problem into a greater number of subproblems improve execution time?
Question
In the lesson on Merge Sort, we implemented merge sort where we divided the array into two parts at each recursion step. Imagine you are asked to implement merge sort by dividing the problem into three parts instead of two. You can assume for simplicity that the input size will always be a multiple of 3. Use a priority queue to merge sub-arrays in the combining step.a- Provide implementation for the 3-way division merge sort.b- Provide a generalized expression for the number of recursion levels.c- Work out the time complexity for the 3-way merge sort.d- Will implementing merge sort by dividing the problem into a greater number of subproblems improve execution time?
Solution 1
a) Here is a Python implementation of a 3-way merge sort:
import heapq
def merge_sort_3way(arr):
if len(arr) <= 1:
return arr
else:
third = len(arr) // 3
left = merge_sort_3way(arr[:third])
middle = merge_sort_3way(arr[third:2*third])
right = merge_sort_3way(arr[2*third:])
return list(heapq.merge(left, middle, right))
arr = [12, 11, 13, 5, 6, 7]
print("Given array is", end="\n")
print(arr)
print("Sorted array is: ", end="\n")
print(merge_sort_3way(arr))
b) The number of recursion levels in a 3-way merge sort can be expressed as log3(n), where n is the size of the input array. This is because at each level of recursion, the problem size is divided by 3.
c) The time complexity of a 3-way merge sort is O(n log3 n). This is because at each level of recursion, we perform n operations (merging), and there are log3(n) levels of recursion.
d) Dividing the problem into a greater number of subproblems does not necessarily improve execution time. While it may reduce the depth of recursion (i.e., the number of recursion levels), it increases the amount of work done at each level of recursion. In the case of merge sort, dividing the problem into more than two subproblems actually increases the time complexity. For example, a 3-way merge sort has a time complexity of O(n log3 n), which is greater than the time complexity of a 2-way merge sort (O(n log2 n)). Therefore, a 2-way merge sort is more efficient.
Solution 2
a- Here is a Python implementation of the 3-way merge sort:
import heapq
def merge_sort_3way(arr):
if len(arr) <= 1:
return arr
else:
mid1 = len(arr) // 3
mid2 = 2 * len(arr) // 3
left = merge_sort_3way(arr[:mid1])
middle = merge_sort_3way(arr[mid1:mid2])
right = merge_sort_3way(arr[mid2:])
return list(heapq.merge(left, middle, right))
arr = [12, 11, 13, 5, 6, 7]
print("Given array is", end="\n")
print(list(arr))
print("Sorted array is: ", end="\n")
print(merge_sort_3way(arr))
b- The number of recursion levels in a 3-way merge sort can
Similar Questions
What is the precise purpose of merge() method in Merge Sort? a. It inserts maximum element from the subarray to the end b. It rearranges all elements according to the pivot point c. It sorts an array using Divide and Conquer concept d. It joins two unsorted subarrays into one e. It joins two sorted subarrays into one
Consider the following array: array = [38, 27, 43, 3, 9, 82, 10].Using merge sort – the first round of the merge sort algorithm will be [38] [27] [43] [3] [9] [82] [10].What will the second round of the merge sort algorithm be:a.[27, 38], [3, 43], [9, 82], [10]b.[38, 27], [43, 3], [82, 9], [10]c.[38,27,43],[3,9,82] , [10]d.[3,27,38], [9,43,82,10]
What is the base case in the Merge Sort algorithm when it is solved recursively?
What is the worst case time complexity of mergesort
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.Merge nums1 and nums2 into a single array sorted in non-decreasing order.The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n. Example 1:Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3Output: [1,2,2,3,5,6]Explanation: The arrays we are merging are [1,2,3] and [2,5,6].The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.Example 2:Input: nums1 = [1], m = 1, nums2 = [], n = 0Output: [1]Explanation: The arrays we are merging are [1] and [].The result of the merge is [1].Example 3:Input: nums1 = [0], m = 0, nums2 = [1], n = 1Output: [1]Explanation: The arrays we are merging are [] and [1].The result of the merge is [1].Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1. Constraints:nums1.length == m + nnums2.length == n0 <= m, n <= 2001 <= m + n <= 200-109 <= nums1[i], nums2[j] <= 109 Follow up: Can you come up with an algorithm that runs in O(m + n) time?
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.