I haven't managed to find this data structure, but I'm not an expert in the field.The structure implements a set, and is basically an array of comparable elements with an invariant. The invariant is the following (defined recursively):An array of length 1 is a merge-array.An array of length 2^n (for n > 0) is a merge-array iff:the first half is a merge-array and the second half is emptyorthe first array is full and sorted, and the second half is a merge-array.Note that if the array is full, it is sorted.To insert an element, we have two cases:If the first half is not full, insert recursively in the first half.If the first half is full, insert recursively in the second half.After the recursive step, if the whole array is full, merge thehalves (which are sorted), and resize it to the double of its originallength.To find an element, recurse in both halves, using binary searchwhen the array is full. (This should be efficient since there areat most $O(\log(n))$ ascending fragments).The structure can be thought as a static version of mergesort.It's not clear what one should do to erase an element.Edit: after improving my understanding of the structure.
I dreamt of a data structure, does it exist?
ds.data structures
You're describing the classical Bentley-Saxe logarithmic method, applied to static sorted arrays.  The same idea can be used to add support for insertions to any static data structure (no insertions or deletions) for any decomposable searching problem.  (A search problem is decomposable if the answer for any union $A\cup B$ can be computed easily from the answers for the sets $A$ and $B$.)  The transformation increases the amortized query time by a factor of $O(\log n)$ (unless it was already bigger than some polynomial in $n$), but increases the space by only a constant factor.  Yes, it can be deamortized, thanks to Overmars and van Leeuwen, but you really don't want to do that if you don't have to.These notes cover the basics.Cache-oblivious lookahead arrays are the mutant offspring of Bentley-Saxe and van Emde Boas trees on steroids.