Please see below assignment problem :-
I have idea of that this will be solved by divide and conquer but can’t figure out the exact way. Please suggest me some algorithm to do this. A proof is really welcome…
You can use counting sort
For all numbes from 1...k, binary search (in Y/N questions) for the number of occurences of the particular number. Just write that number that many times. This would be O(k \log n).
3 Likes
I also had such problem. I found some additional information about binary search at AustralianWritings and this helped me. Just check it and maybe this will help you too.
Not wanting to be a party spoiler but I don’t see any problem XD
1 Like
Sorry, it was really…silly :).
1 Like
This Q blew me up…*hides in a corner from this monstrous 20-question sorting algo"
really?? what is going through your mind…
Thank you. I got it later but not the name:)