ZuoTi.Pro
Question

Mergesort3: Your friend suggests the following variation of Mergesort: instead of splitting the list into two...

Mergesort3:

Your friend suggests the following variation of Mergesort: instead of splitting the list into two halves, we split it into three thirds. Then we recursively sort each third and merge them.

Mergesort3 (A[1...n]):
   If n <= 1, then return A[1..n]
   Let k = n/3 and m = 2n/3
   Mergesort3(A[1..k])
   Mergesort3(A[k+1..m])
   Mergesort3(A[m+1..n)
Merge3(A[1..k], A[k+1,..m], A[m+1..n])
Return A[1..m].


Merge3(L0, L1, L2):
   Return Merge(L0, Merge(L1,L2)).


Assume that you have a function Merge that merges two sorted lists of lengths q and p in time k(q+p) where k is a constant. You may assume that n is a power of 3, if you wish.

(a) What is the asymptotic running time for executing Merge3(L0, L1, L2), if L0, L1, L2 are three sorted lists of length n/3? Give the tightest bound possible. Show your work!

(b) Let T(n) denote the running time of Mergesort3 on an array of size n. Write a recurrence relation for T(n) and solve it using the tightest bounds possible.

(c) Compare the running time of Mergesort3 to the running time of ordinary Mergesort.

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

hiollouoing mergesort of vario on insted of spltting into Lioo haves, use aae spht it into thaec thirds Them we them. oe ecursively sort eoch third and mere Grive function mege that meges uoo Sooted enct h co hetC K is constant abe assuming thet n ts a powe of 3 here uoill dso take on) to mege dll the 1) Thace way merge w thee Sorted axay Fen) -300, by case 3 of mastexs method use get

0 0
Add a comment
Know the answer?
Add Answer to:
Mergesort3: Your friend suggests the following variation of Mergesort: instead of splitting the list into two...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • Consider a variation of Merge sort called 4-way Merge sort. Instead of splitting the array into...

    Consider a variation of Merge sort called 4-way Merge sort. Instead of splitting the array into two parts like Merge sort, 4-way Merge sort splits the array into four parts. 4-way Merge divides the input array into fourths, calls itself for each fourth and then merges the four sorted fourths. a) Give pseudocode for 4-way Merge sort. b) State a recurrence for the number of comparisons executed by 4-way Merge sort and solve to determine the asymptotic running time.

  • Consider a variation of Merge sort called 4-way Merge sort. Instead of splitting the array into...

    Consider a variation of Merge sort called 4-way Merge sort. Instead of splitting the array into two parts like Merge sort, 4-way Merge sort splits the array into four parts. 4-way Merge divides the input array into fourths, calls itself for each fourth and then merges the four sorted fourths. a)Implement 4-way Merge sort from Problem 4 to sort an array/vector of integers and name it merge4. Implement the algorithm in the same language you used for the sorting algorithms...

  • 2. Here is a sorting algorithm that I like to use. Given an unsorted list of...

    2. Here is a sorting algorithm that I like to use. Given an unsorted list of size n, let Xx represent the data in location k of the unsorted list. Compare xi to X2 and switch if necessary so that they are in sorted order, smallest first. Compare Xn-1 and Xn and switch if necessary so that they are in sorted order, smallest first. • Compare x3 with its left neighbors, switching if necessary so that the 3 first entries...

  • #include <sys/types.h> #include <sys/ipc.h> #include <sys/shm.h> #include <sys/wait.h> #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include<time.h> void...

    #include <sys/types.h> #include <sys/ipc.h> #include <sys/shm.h> #include <sys/wait.h> #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include<time.h> void insertionSort(int arr[], int n); void merge(int a[], int l1, int h1, int h2); void mergeSort(int a[], int l, int h) { int i, len=(h-l+1); //Using insertion sort for small sized array if (len<=5) { insertionSort(a+l, len); return; } pid_t lpid,rpid; lpid = fork(); if(lpid<0) { //Lchild proc not created perror("Left Child Proc. not created\n"); _exit(-1); } else if (lpid==0) { mergeSort(a,l,l+len/2-1); _exit(0); } else...

  • Could somebody please help. Thanks in advance! Merge two sorted linked lists and return it as...

    Could somebody please help. Thanks in advance! Merge two sorted linked lists and return it as a new list. 1) Implement a method: mergeTwoLists(…){…} 2) Use the LinkedList library in Java 3) Test your method. Example: Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4 ````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````` import java.util.*; public class Inclass1 { public static void main(String[] args){ //Question 5.2 LinkedList l1 = new LinkedList<>(); LinkedList l2 = new LinkedList<>(); l1.add(1); l1.add(2); l1.add(10); l2.add(1); l2.add(3); l2.add(4); LinkedList l3 = mergeTwoLists(l1, l2); System.out.println("Question \n******************************"); for(int i...

  • Suppose the following is a divide-and-conquer algorithm for some problem. "Make the input of size n...

    Suppose the following is a divide-and-conquer algorithm for some problem. "Make the input of size n into 3 subproblems of sizes n/2 , n/4 , n/8 , respectively with O(n) time; Recursively call on these subproblems; and then combine the results in O(n) time. The recursive call returns when the problems become of size 1 and the time in this case is constant." (a) Let T(n) denote the worst-case running time of this approach on the problem of size n....

  • For each of the following problems write a recurrence relation describing the running time of eac...

    For each of the following problems write a recurrence relation describing the running time of each of the following algorithms and determine the asymptotic complexity of the function defined by the recurrence relation. Justify your solution using substitution and carefully computing lower and upper bounds for the sums. Simplify and express your answer as Θ(n k ) or Θ(n k (log n)) wherever possible. If the algorithm takes exponential time, then just give exponential lower bounds. 5. func5 (A,n) /*...

  • And the related algorithms: (20 points) Consider the following strategy for choosing a pivot element for...

    And the related algorithms: (20 points) Consider the following strategy for choosing a pivot element for the Partition subroutine of QuickSort, applied to an array A. .Let n be the number of elements of the array A. If n 24, perform an Insertion Sort of A and return. Otherwise: Choose 2n/2)| elements at random from n; let S be the new list with the chosen elements. Sort the list S using Insertion Sort and use the median m of S...

  • For each of the following problems, simplify and express your answer as Θ(nk) or Θ(nk(log n...

    For each of the following problems, simplify and express your answer as Θ(nk) or Θ(nk(log n wherever possible. If the asymptotic running time is exponential, then just give exponential lower bounds. Random(n) generates a random number between 1 and n with uniform distribution (every integer between 1 and n is equally likely.) CoinFlip) returns heads or tails with equal probability. Consider the following ution: Func5 (A, n) A is an array of inlegers 1 if (n <10 the retur (A])...

  • you will analyse two algorithms for finding the median of an array of integers. You will...

    you will analyse two algorithms for finding the median of an array of integers. You will compare both algorithms in terms of timing, and hopefully design a hybrid algorithm that uses both, depending on input size. You will write a report describing your experiments and results. the following Java program implements two algorithms for finding the median of an array of integers. The first uses merge sort, and the other implements the recursive linear time selection algorithm, the task is...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT