Merge sort and insertion sort

Question

Comments

@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).