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.

• Can a register store multiple key-value pairs? If not, what do you mean by "when popping from one of these registers, it will return the smallest key"? Oct 9 '18 at 3:49
• @xskxzr one register can only hold one key-value pair. What I mean by the smallest key, is say the registers had 3 keys [5,8,9] when you call pop, the register will return the key 5 since it is the smallest. Oct 9 '18 at 15:02
• As an informal idea: with k registers, you can sort k items in O(k) time. You can sort k^2 registers in 2*k^2 time (by first sorting k subgroups and then doing a merge of k groups). Similarly k^3 in 3*k^3.... Then we can sort k^x = n registers in n * log n / log k time Oct 9 '18 at 19:44