I'm stuck on a question and I just need a hint/point in the general direction (not asking for the answer)
The question asks for the details of a divide and conquer algorithm that given a sequence that is almost sorted, produces the correct order in time O(n).
What they mean by almost sorted is that given the list
x_1, x_2, .... x_n
if the sorted list is represented by
y_1, y_2, ... y_n
and for every i, j <= n this property is respected:
x_i == y_j && |i-j| <= root(n)
The only thing that came to my mind was to divide the lists into root(n) groups at each level (which would cause them to be at most length root(n) for the first split), but I'm not too sure where to go from there, because you'd have to join up root(n) elements at a time as you recurse back up.
I've also figured out that the recursion complexity equation would be:
T(n) = root(n) * T(n/root(n)) + d * root(n)
which by the master's theorem can be proved to be O(n) time.
So it kind of seems like I'm on the right track with the splitting, I'm just not sure if it should be split up in a special way or compared a certain way or what.
EDIT: So supposedly this was the correct answer.
Our algorithm is as follows: If n > 1, then we recursively sort each of the two (approximate) halves of the sequence; now all the elements are in the correct position, except possibly those within √n positions of the middle (do you see why this is true?); so we now do a merge of the elements in those positions. If we let T(n) be the time used to sort nelements, then for n > 1 we have
T(n)≤2T(⌈n=2⌉) +c * √n
Since √(n) = n.5 and .5 < 1 = log22, the Master Theorem for Divide and Conquer Recurrences tells us thatT(n)∈O(n).
I'm not sure if I agree since the time to sort both halves would be O(n⁄2 * log(n⁄2)) which works out to be O(n*logn) and the final merge would be O(√n * √n) which is O(n) giving us a total of O(n*logn + n) -> O(n*logn)
Such an algorithm could be used to sort r lists of r items in O(r*r) time, just by concatening the lists (and decorating the elements, if necessary). However, it is known that you can't do better than O(r*r*ln(r)), or O(n * ln(n)) for n = r * r.
I guess that either the original question is a littledifferent, or that the person giiving the original question to you made a mistake when calculating the complexity. Like, for example, assuming that when the list is divided in two halves, both parts are still almost sorted. (There are ways to split up the list in this way, like taking every second element, but not every partition of the list will have this property.)