2 Combined Algorithm

Consider a modification to merge sort in which n/k sublists of length k are sorted using insertion sort and then merged using the standard merging mechanism, where k is a value to be determined. 1 2.1

Required Work 2

1. Show that insertion sort can sort the n/k sublists, each of length k, in (nk) worstcase time.

Insertion sort takes O(K²) time per K-element in worst case time. Therefore sorting n/k such K-element lists, takes O(K²n/K)=O(nK) worst case time.

2. Show how to merge the sublists in (n lg(n/k)) worst-case time. Hint: merging the n/k sublists will be done by stages. In every stage we merge two sublists by two until we arrive to the final stage with 2 sublists of size n/2 each. Think about how many stages are there and how many numbers need to be merged at every single stage.

The key idea is to merge the list pair wise, then merge the resulting lists pair wise until there is only one list . the pair wise merging requires O(n) work each level ,since we are still working on n elements, even if they are petitioned among sub lists. The number of levels ,starting with n/k, K-element list and finishing with 1n-element list, is [n lg(n/k)]

,therefore the total running time for the merging is O(n lg (n/k))

3. Given that the modified algorithm runs in (nk + n lg(n/k)) worst-case time, what is the largest value of k as a function of n for which the modified algorithm has the same running time as standard merge sort, if we suppose that (nk +n lg(n/k)) can be approximated by either (nk) or (n lg(n/k))?

The largest asymptotic value of k₁ for which the modified algorithm has the same asymptotic running time as slandered merge sort , Is K= O(lg n). the combined running time is O(n lg n +n lg n- nlg lg n), which is O(n lg n) for the larger value of K the term nk would be larger than (n lg n)

4. How should we choose k in practice?

In practice ,k should be chosen such that is minimalize the running time of combined algorithm.

If assign the number of data to x-axis and the consumed time to y-axis I can draw:

C₁ .x lg x and C₂ . x² graphs ,there should be an intersection point determined by C₁ and C₂ . which represent the data number that the merge sort is firstly faster than insertion sort. So it is natural to choose the x-value of the intersection point as k. it is well known that the insertion sort is the faster one when n<= 16 , so we could say k is 16 experimentally.

can you explain my way use 16 and can I use 50