What does it mean when each individual array is sorted in different array but bear no relationship to each other

Question

There's a textbook problem that talks about making a binary search dynamic, then analyzing for its amortize cost. However I'm not exactly sure what is the organization scheme of this data structure.

Binary search of a sorted array takes logarithmic search time, but the time to insert a new element is linear in the size of the array. We can improve the time for insertion by keeping several sorted arrays. Specifically, suppose that we wish to support SEARCH and INSERT on a set of $n$ elements. Let $k = lg(n + 1)$, and let the binary representation of $n$ be $\langle n_{k‒1}, n_{k‒2}, \ldots , n_0 \rangle$. We have $k$ sorted arrays $A_0, A_1, \ldots , A_{k‒1}$, where for $i = 0, 1, \ldots , k − 1$, the length of array $A_i$ is $2i$ . Each array is either full or empty, depending on whether $n_i = 1$ or $n_i = 0$, respectively. The total number of elements held in all $k$ arrays is therefore $n$. Although each individual array is sorted, elements in different arrays bear no particular relationship to each other

(Excerpt From: Thomas H. Cormen et al., “Introduction to Algorithms: Third Edition.”)

What does this mean when we have a data structure with several sorted arrays that bear no such relationship? Does it mean that they all must be sorted relative to themselves, but not to the rest? If that's the case, when you try to perform an insert or delete, conceptually, how would you know which array to insert it to or to delete from, and how would it be reshaped?

Answer 1

What they mean is exactly that: the invariant maintained by the data structure is that each of the arrays $A_0,\ldots,A_{k-1}$ is sorted. Nothing is maintained regarding the relative order of elements in different arrays.

The text probably goes on to describe how to perform the search, insert and delete operations. The search operation is simple: you just search the individual arrays. To insert an element, there are two cases: if $n$ is even, we just add a new array $A_0$ with the new element. Otherwise, choose the smallest $i$ such that $n_i = 0$ (possibly $i=k$). We add the new element to $A_0$, and then merge $A_0,\ldots,A_{i-1}$ to $A_i$ (in this order: merge $A_0$ and $A_1$ to $B_1$; merge $B_1$ and $A_2$ to $B_2$; and so on). Element deletion is more complicated; the data structure is only supposed to support search and insert.

The key idea is that when inserting an element, it is we (the designers of the data structure) who choose where to put it.

The text probably goes on to analyze the amortized cost of these operations. I'll leave these details to the text. (Unless it's an exercise, in which case you should work them out!)