I am trying to figure out a sorting algorithm which can be used in $O(n\frac{\log{n}}{\log{k}})$ sorting time. I am allowed to use $k$ registers that can store key value pairs and these registers can insert a key value pair and return a key value pair in constant time. And when popping from one of these registers, it will return the smallest key. So what I have so far is, I am thinking about having a hash function with value (highest value in array size n) and then put that into the registers, then will pop the registers (Which will return the smallest key value) and then add those sorted, values back into the array. But the main problem I have is I do not know how large $k$ will be so when I pop the values from the registers, I may have to put more values back in the registers, and was wonder how to go about this. Login To add answer/comment