Blind sorting an array with a singular sort function?

Question

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?

Answer 1

Your approach by mimicking Bubble Sort is pretty good.

Here is a hint. Since we can sort a block, we can raise half a block of the largest elements so far like a bubble each time. For example, when $u=5$, if we have done BlockSort on [0,5], [3,8] and [6,11] successively, we will have placed the largest 6/2=3 elements among the first 12 elements at index 9,10 and 11, the end of subarray so far.