I’m trying to solve this problem:

Consider an array A of length n, where:

• each element contains an integer-valued key and additional satellite data
• there are exactly k distinct key values
• k ∈ Θ(log n)

Describe a stable sorting algorithm that sorts A with a run time complexity in Θ(n log log n).

How can I do this?

I have something in mind using bucketsort, but I’m unsure if it satisfies the requirements.