Merge sort and insertion sort

Question

Comments

//i am writing just a pseudocode
k=n
mrgshort(n)
{
  if(n<=k/2^r) 
    O(n^2); 
  else
 {
   mrgshort(n/2); 
   mrgshort(n/2); 
   O(n); 
 } 
}

now, you can easily see if() part is approximately contributing to O(n²) and,

else{ } part is contributing about O(nlogn),

so overall time complexity = O(n²)

PS: understanding the time complexity of above code is little triky but if you will analyze carefully, you will find what i have said.

---

can u please explain how did u come up with the if() part?

---

it goes till r th level,then we do insertion sort and merge back right?. But at rth level the size of each sublist will be r, that means insertion sort would contribute r^2 (for each sublist) * 2^r (no of sublists) and then merge back,how can it be as large as Theta (n^2) ?? The options should have in the order of constants.Imagine the following, n = 256.

Sublist size initial = 256

1st recursion = 128,128

2nd recursion = 64,64,64,64

3rd recursion = 16,16,16,16 16,16,16,16 16,16,16,16 16,16,16,16

Suppose we stop now ,notice we have size 16 sublists of size 16. Which if we use insertion sort will take cost as 16^2 * 16 .Then we merge back.How can it be as large as n^2 ??..Then why to use merge sort ,use direct insertion sort in the intial list itself.

---

@Surajit

But at rth level the size of each sublist will be r, that means insertion sort would contribute r^2 (for each sublist) * 2^r (no of sublists) and then merge back

at rth level size of each list will be $\frac{n}{2^{r}}$ and we have total of  2^r list,

therefore total time taken to perform insertion sort on 2^r lists will be 2^r * ($\frac{n}{2^{r}}$)² = O(n²)

---

yes correct,my mistake in calculation.But this is kind of increases complexity of the program itself,asymptotically a direct insertion sort might have produced same result maybe added few more constant terms.

---

If one can get a sublist of size of 2^r and no of sublist as n/2^r then I think we can perform better.(Just a thought,out of the context of the questions given).