3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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"? $\endgroup$
    – xskxzr
    Oct 9, 2018 at 3:49
  • $\begingroup$ @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. $\endgroup$
    – Ryan w
    Oct 9, 2018 at 15:02
  • $\begingroup$ 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 $\endgroup$
    – Lawrence
    Oct 9, 2018 at 19:44

1 Answer 1

Reset to default
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.