Consider the following variation of merge sort: split the list into thirds, sort each third, and...

Consider the following variation of merge sort: split the list into thirds, sort each third, and then merge all three sorted lists.

(a) Write pseudo-code for this sorting algorithm in python.

(b) Write a recurrence relation for the run-time of this algorithm, and use the master theorem to find the “big O” run time of the algorithm.

(c) How does the run time compare to the usual merge sort? Is this an improvement?

Expert Solution

The solution in the images below and let me know of the issues you are facing in the comments below.

The form of master theorem is given below

c) The running time is same as the original merge sort which also has the run time of the order of θ(nlogn) . Hence, it is not an improvement over the ordinary merge sort

venereology answered 5 months ago

Java program to implement the merge sort your own and test it to sort a list...

Java program to implement the merge sort your own and test it to sort a list of names based on the frequency.

Which of the following sorting algorithms are stable: insertion sort, selection sort, merge sort and quick...

Which of the following sorting algorithms are stable: insertion sort, selection sort, merge sort and quick sort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?

Question: Consider the following variation of insertion sort: For 1 ≤ i < n, to insert...

Question: Consider the following variation of insertion sort: For 1 ≤ i < n, to insert the element A[i] among A[0] ≤ A[1] ≤ … ≤ A[i-1], do a binary search to find the correct position for A[i]. a. How many key comparisons would be done in the worst case? b. How many times are elements moved in the worst case? c. What is the asymptotic order of the worst case running time?

1.)recursive merge sort on a list.(Python) 2.)recursive bubble sort using a list without enumerate() function.(python) Show...

1.)recursive merge sort on a list.(Python) 2.)recursive bubble sort using a list without enumerate() function.(python) Show Base case, and recursive case.

Consider a sorting algorithm that combines merge sort and insertion sort algorithm. We still use divide...

Consider a sorting algorithm that combines merge sort and insertion sort algorithm. We still use divide and conquer like merge sort, however when the number of elements in an array is at most k elements (k is a parameter), we stop dividing the elements as the regular merge sort, instead, we call the insertion sort. Assuming we have defined the following two procedures: insertion-sort(A[p..q]) which sort the subarray A[p..q] merge(A[p,q,r]) which merges the sorted subarray A[p..r] and A[r+1..q] Try to...

Given two sorted linked lists, merge them into a third sorted linked list. If an element...

Given two sorted linked lists, merge them into a third sorted linked list. If an element is present in both the lists, it should occur only once in the third list. Code needed in java.

(Write a C# program DO NOT USE CLASS)Implement the merge sort algorithm using a linked list...

(Write a C# program DO NOT USE CLASS)Implement the merge sort algorithm using a linked list instead of arrays. You can use any kind of a linked structure, such as single, double, circular lists, stacks and/or queues. You can populate your list from an explicitly defined array in your program. HINT: You will not be using low, middle and high anymore. For finding the middle point, traverse through the linked list while keeping count of the number of nodes. Break...

1. For each of the following lists, perform a bubble sort, and show the list after...

1. For each of the following lists, perform a bubble sort, and show the list after each exchange: D,B,G,F,A,C,E,H 2. Explain why the bubble sort algorithm does O (n^2) comparisons on an n-element list.

Analyze the time complexity of the following variant of merge sort: given a constant k, divide...

Analyze the time complexity of the following variant of merge sort: given a constant k, divide the array into k parts, sort each part recursively, and merge the results.

Write a program including binary-search and merge-sort in Python. it has to output the following: NeArr range(0,...

Write a program including binary-search and merge-sort in Python. it has to output the following: NeArr range(0, 20) result for searching 6 True result for searching 16 False for-loop's function arr range(0, 15) for-loop's func result for searching 6 1 result for searching 16 0 it has to be a simple code and please!! put the whole code together.

Question