INSERTION-MERGE-SORT(A, P, r) if p key A[i + 1] = A[i] i = i - 1 A[i + 1] = key

Question

INSERTION-MERGE-SORT(A, P, r) if p key A[i + 1] = A[i] i = i - 1 A[i + 1] = key MERGE(A. p. q. r ) n1 = q - p + 1 n2 = r - q let L[1 . . n1 + l] and R [1 ..n2 + 1) be new arrays for i = 1 to n2 R[j] = A[q + j ] L[n1 + 1] = infinitive R[n2 + 1] = infinitive i = 1 j = 1 for k = p to r if L [ i ] R(j) A[k] = L[i] i = i + 1 else, A[k] = R[j] j = j + 1 Prove that INSERTIONMERGE solves the same problem as the MERGE algorithm but works in place. Hint: use a loop invariant. Prove that INSERTION-MERGE-SORT sorts the input array A. Hint: use induction. Identify the best and worst case of INSERTIONMERGE mid compute the runtime T(n) in asymptotic notation for each. Be explicit about summing the number of iterations in the loops.

Explanation / Answer

fun split(lst:int list):int list * int list = fold (fn (x, (left,right)) => (right,x::left)) ([],[]) lst fun merge(left:int list,right:int list):int list = case (left,right) of (nil,_) => right | (_,nil) => left | (x::xs,y::ys) => if x [] | [x] => [x] | _ => let val (left,right) = split lst val lsorted = msort left val rsorted = msort right in merge(lsorted,rsorted) end We need to know the recurrence relations and running times for split and merge. You should be able to prove that the running times of both are O(n), where merge(l,m) is merging two lists of length n/2. We will now use this information to prove the running time of msort is n log(n) + n = O(n log n). First, we must determine the recurrence relation: T(1) = c1 T(n) = Tsplit(n) + 2*T(n/2) + Tmerge(n) Note that we make an assumption that split splits a list of length n into two lists each of length n/2. To be complete, one would have to prove that this is true. For now, we will just prove that the running time is O(n log n): Claim: For all n > 128, the running time of msort(l) is runs in n log n time, i.e., T(n) ? n log n + n, where the length of l is n. Proof by induction on n Base Case: n = 1: T(1) = 1 = 1 log 1 + 1 Induction Hypothesis: Assume that for arbitrary n, T(n) ? n log n + n Prove T(n+1) ? (n+1) (log (n+1)) + (n+1) T(n+1) = Tsplit(n+1) + 2*T((n+1)/2) + Tmerge(n+1) ? Tsplit + ((n+1) (log (n+1)/2)) + Tmerge(n+1) By Induction Hypothesis ? 2((n+1)/2 (log (n+1)/2) + (n+1)/2) + (n+1) where Tmerge + Tsort = (n+1) ? (n+1) log (n+1) + (n+1) Thus, we can conclude that the running time of msort is O(n log n).

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.