Is there a $O(n\frac{\log{n}}{\log{k}})$ sorting algorithm? 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 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.
So the answer I ended up going with is making the value the key itself, then adding the key and the value to the registers. Once the registers are full, we will pop the smallest key, and do a binary search on where we should be inserting the value into a new sorted array which we will be returning.