You don't specity if you want an in-place solution or not. I assume not.
You need to keep one running index per bucket, knowing the range of indexes that every bucket can span. Use an array of indexes, one per bucket.
Start with all indexes in their lower value.
Repeatedly pick the bucket where the current element is the smallest, output this element and increase the index of this bucket. (When any index has reached its highest value, make as if the next value was + infinity.)
You are done when all indexes have reached their highest value.
In order to find the smallest element amont the buckets, you have two options:
- if the number of buckets is small (say < 10), just use a linear search for the minimum (skipping the exhausted buckets);
- otherwise use a priority queue for this purpose, storing pairs with value/bucket index.
http://en.wikipedia.org/wiki/Priority_queue#Usual_implementation[
^]. Implementation details are more involved.