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 while problem size equals cache memory).
Best case and worst case running time of the algorithm respectively is:
A) 2k-5 [1+log22k-5], 2k-5 [25+log22k-5]
B) 2k-5 [1+log22k-5], 25 [2k-5+log22k]
C) 2k [1+log22k-5], 2k [25+log22k-5]
D) 2k [25+log22k-5], 2k [25+log22k-5]