I am doing some interview prep, and I came across a question that really stumped me, and it didn't provide an answer.
The premise of the question was as follows:
You are given some unsorted array A of size n. You are not allowed to access the array, read values, or compare the values.
The only manner in which you may interact with said array is with a BlockSort() functions, such that calling BlockSort(index) will automatically sort the elements within the inclusive bounds of [i,i+u] for some arbitrary but fixed u, such that u≥1.
Sort A with O((n/u)^2) calls to BlockSort.
My initial approach to this question was to mimic Bubble Sort, except stagger the calls to BlockSort, such that each successive call overlaps with one element of the previous call, (i.e. BlockSort(0,u), BlockSort(u,2u)...etc.) and then after iterating like that through the array once, you are left with the global maximum at the end of the array, and an unsorted array of size n-1, and then you can recursively solve the problem.
This has a time complexity of O((n^2)/u) though.
I have thrown an hour or 2 at the problem, and I can't quite see how they achieved O((n/u)^2).
Is there anything I could think about to get to the answer?