sorting algorithm

[boris86]

a.Given n integers, describe an algorithm (in pseudo-code or in clear
words), that performs a partial sort: the algorithm should divide the input
into groups of 5, such that the numbers within each group are not
necessarily sorted, but the groups are sorted between them (that is, all of
the numbers in a group are larger than the numbers in the previous group,
and smaller than the numbers in the next group). Formally, let 1 /5 ,..., n S S
be the resulting sets of elements, each consisting of 5 elements, then:

For example:
Input: 1, 22, 5, 23, 7, 12, 4, 16, 8, 24, 15, 2, 11, 3, 9
Output: 3, 4, 2, 5, 1, 9, 7, 12, 8, 11, 15, 22, 23, 24, 16

What is the complexity of your algorithm?
b. Assuming that we have no prior knowledge on the input numbers, is it
possible to solve the above problem in O(n·log log n)? Describe an
algorithm, or prove that one does not exist.

thanks for the help

[nuzzle]

Describe an
algorithm, or prove that one does not exist.


One way is to make a full sort, it's a special case of a partial sort. A full sort is O(N*logN) so that's the worst complexity there's going to be.

Note that there isn't always a solution and that's when you have repeated numbers. If a number is repeated more than 5 times this number will be in two consecutive groups. It will be the largest in one group and the smallest in the next. This violates the criterion that ALL numbers of a group must be smaller than ALL in the next. They aren't because some numbers will be equal. And even if a number is just repeated twice you may end up having to split them into different groups to fulfill the criterion that there should be exactly 5 numbers in each group.

To me it seems repeated numbers are something of a big problem here. It's kind of strange that all numbers in the example are unique. Is this on purpose or is it an oversight?