An interesting data structure with search time O(sqrt n)

[Emil Kirschner via Digitalmars-d]

On Monday, 30 November 2015 at 20:13:15 UTC, Andrei Alexandrescu 
wrote:
> Okasaki's book is a continued inspiration of data structures 
> and algorithms.
> Start with a simple array of data. Then mentally decompose that 
> array into a concatenation of smaller arrays: first has size 1, 
> second has size 4, third has size 9, then 16, 25, 36, ... 
> Generally the size of these imaginary subarrays grows 
> quadratically. And they're adjacent to each other. The last 
> array may be incomplete.
> ........
> Please share any thoughts!
>
>
> Andrei

Interesting, but isn't that basically a skip list with uneven 
sub-lists? insert could be quite complex unless the entire data 
structure is backed by a continuous or a continuous linked list.