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 empty or
- the 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 the halves (which are sorted), and resize it to the double of its original length.
To find an element, recurse in both halves, using binary search when the array is full. (This should be efficient since there are at 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.