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 upI'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
Divide and conquer algorithm to sort a list where each element is root(n) away from its sorted position
ds.algorithms