Suppose that you are given a sequence of n elements to sort. The input sequence consists of n=k subsequences, each containing k elements.The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the elements in the preceding subsequence.
So is there a O(nlogk) method to put a disordered array to an array described above? thx!
A different formulation of the question
The question can be thought of like this. You have n balls of different sizes. You want to organize these into n/k buckets such that each bucket contains exactly k balls. Furthermore these buckets are placed in a line in which the left most bucket contains the k smallest balls. The 2nd bucket from the left contains the next k balls that would have been the smallest if we were to remove the leftmost bucket. The rightmost bucket contains the k largest balls.
But within each bucket you have no order. If you want the largest ball you know which bucket you must begin searching in, but you still need to search around in it.
I will be using the term bucket instead of subsequence since subsequence makes me think about ordering which is not important, what is important is belonging so bucket is easier for me.
A problem with the proposed complexity of the imagined solution
You are stating that k is the length (or size) of each bucket. It therefore naturally can be between 1 and n.
You then ask for if a O(n log k) solution exists that can organize the elements in this manner. There is a problem with your proposed complexity that is easy to see when we consider the two extremes k=1 and k=n.
k=n. Meaning we only have one large bucket. This is trivial since no action is needed. But your proposed complexity was O(n log k) = O(n log n) when k = n.
Let us consider k=1 too because it has a similar, but inverse, issue.
k=1. Each bucket contains 1 ball, and we need n buckets. This is the same as asking us to fully sort the whole sequence which will at best be O(n log n). But your proposed complexity was O(n log k) = O(n log 1) = O(n * 0) = 0. Remember log 1 = 0. It seems that your proposed complexity does not fit the problem at all.
We can pause here and say. No, you cannot do what you wish on O(n log k) because it does not make sense that the problem would become harder when you decrease the number of buckets. More importantly it cannot become easier as you increase the number of buckets.
If I were tasked to do this sorting manually I would say is trivial to sort into one bucket. Two is easy. Three would be harder than two. If you have n buckets then that is as hard as it can get!
Answer for an altered complexity It is however interesting to consider what would happen if we were to fix your proposed complexity so that we instead ask the following. Is there a way to sort into these buckets in O(n log b) where b is the number of buckets (b = n / k)?
The extreme cases here seem to make sense.
b=1. One bucket. No sorting needed. O(n log b) = O(n log 1) = O(0). (technically this should still maybe be O(1))
b=n. n buckets. Full sort needed. O(n log b) = O(n log n).
So a solution seems possible. But this is outside the scope of the question now. I however suspect that Selection Algorithms and quickselect are the way to go.
