I am preparing some interviews and I came across a question that really shocked me, and that did not provide me with an answer.
The premise of the question was:
You receive an unsorted A chart of size n. You are not allowed to access the table, read values or compare values.
The only way you can interact with this array is to use a BlockSort () function, so that the BlockSort (index) call automatically sorts the elements within the inclusive limits of [i,i+u] for some u u arbitrary but fixed, such as u≥1.
Sort A with O ((n / u) ^ 2) calls to BlockSort.
My initial approach to this issue was to emulate bubble sorting, with the exception of blocking calls to BlockSort, so that each successive call overlaps an element of the previous call (for example, BlockSort (0, u ), BlockSort (u, 2u) .. .etc.) Then, after having iterated once in this way in the table, you end up with the global maximum at the end of the array and an unsorted array of size n-1 , and then you can solve the problem recursively.
This has a time complexity of O ((n ^ 2) / u) however.
I threw an hour or so on the problem, and I do not see how they managed to get O ((n / u) ^ 2).
Is there anything I could think of to get to the answer?