I am not sure my approach is correct or not but I have seen something like this in CLRS.
When we represent nk/2 and nk in base n, we need atmost k+1 bits.
And to sort k+1 bit positions apply any stable sorting algorithm like counting sort(O(n) time ).
So, time complexity = O(k*n) i.e. apply counting sort for each of the k+1 bit positions.
So, answer (b).
If my approach is wrong,can anyone explain why ??