A cache aware sorting algorithm sorts an array of size 2k with each key of size 4 Bytes. The size of the cache memory is 128 Bytes and algorithm is the combination of merge sort and insertion sort to exploit the locality of reference for the cache memory(i.e. will use insertion sort when problem size equals cache memory).
Worst case running time of the algorithm is:
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]\)
3
\({2^5}\left[ {{2^{k - 5}} + {{\log }_2}{2^k}} \right]\)
4
None of the above
5
Question Not Attempted