IITD2011 Interview

Question

#IITD_2011 why dont we divide array in 5 parts for merge sort ?

Answer 1

dividing into many parts does not change the complexity of the algorithm.

dividing into 5 parts makes it O(log₅n) that is O(log₂n) or O(log n)

ps: log₅n= log₂n / log₂5 ;here log₂5 is a constant factor that we can ignore.this is the reason why we dont specify the base of log in O() notation.

so dividing into 5 parts does not change the complexity but the divide step to divide into 5 parts might be slower than that to divide into 2 parts and create further overhead in the algorithm. so we dont usually divide into more than 2 parts unless needed.

Answer 2

merge sort follows divide and conquer programming paradigm.the steps are 1)divide 2)solve sub problems 3) combine

the division step will still take o(1).

now,combine step will take o(n).

it simply will compare top element from 5 sorted sub arrays and put into temporary array.each element is compared with 4 other elements and we find min of those elements.so it take 4 comparsion instead of simply one in case of normal merge sort in worst case

so simply discard the constant.

if  you could understand the above explanation then deriving this would be easy task 4*N*logN/log5

Comments

how dividing an array into 2 parts and 5 parts will take same time?as for divinng into 2 parts,we just need middle element,but thats not for div into 5 parts