# Question: Although merge sort runs in n lg n worst case time

Although merge sort runs in Θ (n lg n) worst-case time and insertion sort runs in Θ(n2) worst-case time, the constant factors in insertion sort make it faster for small n. Thus, it makes sense to use insertion sort within merge sort when sub problems become sufficiently small. Consider a modification to merge sort in which n/k sub lists of length k are sorted using insertion sort and then merged using the standard merging mechanism, where k is a value to be determined.

a. Show that the n/k sub lists, each of length k, can be sorted by insertion sort in Θ (nk) worst-case time.

b. Show that the sub lists can be merged in Θ (n lg (n/k) worst-case time.

c. Given that the modified algorithm runs in Θ(nk + n lg (n/k)) worst-case time, what is the largest asymptotic (Θ notation) value of k as a function of n for which the modified algorithm has the same asymptotic running time as standard merge sort?

d. How should k be chosen in practice?

a. Show that the n/k sub lists, each of length k, can be sorted by insertion sort in Θ (nk) worst-case time.

b. Show that the sub lists can be merged in Θ (n lg (n/k) worst-case time.

c. Given that the modified algorithm runs in Θ(nk + n lg (n/k)) worst-case time, what is the largest asymptotic (Θ notation) value of k as a function of n for which the modified algorithm has the same asymptotic running time as standard merge sort?

d. How should k be chosen in practice?

**View Solution:**## Answer to relevant Questions

Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin's value is an integer.a. Describe a greedy algorithm to make change consisting of quarters, dimes, nickels, and ...Consider the problem of neatly printing a paragraph on a printer. The input text is a sequence of n words of lengths l1, l2, ..., ln, measured in characters. We want to print this paragraph neatly on a number of lines that ...Show that if (S, ℓ) is a matroid, then (S, ℓ′) is a matroid, where ℓ′ = {A′: S - A′ contains some maximal A ¬ℓ}. That is, the maximal independent sets of (S, ...Consider an ordinary binary min-heap data structure with n elements that supports the instructions INSERT and EXTRACT-MIN in O (lg n) worst-case time. Give a potential function Φ such that the amortized cost of INSERT ...We are given a directed graph G = (V, E) on which each edge (u, v) ¬ E has an associated value r(u, v), which is a real number in the range 0 ≤ r(u, v) ≤ 1 that represents the reliability of a communication ...Post your question