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 list that is almost sorted, runs in time $O(n)$.
What they mean by almost sorted is that given the list $x_1, x_2, \ldots, x_n$, if the sorted list is represented by $y_1, y_2, \ldots, y_n$ and for all $i, j \le n, x_i = y_j: |i-j| \le \sqrt n$.
The only thing that comes to mind is dividing the lists into $\sqrt n$ groups at each level (which would cause them to be at most length $\sqrt n$ for the first split), but I'm not too sure where to go from there. You'd have to join up $\sqrt n$ elements at a time as you recurse back up
I've also figured out that the recurrence would be: $T(n) = \sqrt{n} \cdot T(\sqrt n) + d \sqrt n$ which by the master's theorem is $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 a special way or compared a certain way or what.
Thanks in advance