Merge sort

Question

Comments

n strings each of length n so,total elements =n²

We need to combine level by level till we get 1 list (sorted)

Each level cost=n²

number of levels = log (n²) or 2log(n)

total complexity = O(n²logn)

a=2 ; b=1

---

Refer this: https://gateoverflow.in/1762/gate2012_39

Answer 1

It is similar to radix sort , example you need to sort 123 ,456. 124 so you sort the third position and then second and finally the first so but to sort these positions you need a sorting algorithm which is satble, In the above question there are n positions and n characters to sort so it will be n * nlogn so it will be 2+1*(100) = 102

Answer 2

The first character of each n strings to sort it will take O(nlogn) time..in the worst case we may have to do the above process 2 times,3 times,........,n times so n*O(nlogn)=O(n^2 logn)

therfore a=2 and b=1 hence 2+100=102..