Combined Sorting closed

Question

A cache aware sorting algorithm sorts an array of size $2^{k}$ with each key of size 4 Bytes. The size of cache memory 128 Bytes. and algorithm is a combination of merge sort and insertion sort to exploit locality of reference for the cache memory(i.e. will use insertion sort when problem size equal to cache memory)

Worst case running time of this algo

1)$2^{k}\left [ 2^{5}+log_{2}2^{k-5} \right ]$

2)$2^{k-5}\left [ 2^{5}+log_{2}2^{k-5} \right ]$

Comments

https://gateoverflow.in/99455/sorting-algorithm

---

is it O(32*(k-5)*2^k-5)=  O(k2^k)  ??

---

@ joshi_nitish
plz explain ur procedure
atleast with some hint
otherwise how can we tell right or wrong?

---

it is like breaking array of size 2^k into 2^k-5 arrays of size 2⁵, now

each of 2^k-5 arrays of size 2⁵ will be sorted using insertion sort taking 2¹⁰ time for each,

now apply merging algorithm just like huffman coding to merge these 2⁵ sorted arrays..