You can split a collection of 2^(k-1)<=N<2^k elements into up to k arrays with length 2^i. Insertion into empty array with one element capacity is easy, inserti

You can split a collection of 2^(k-1)<=N<2^k elements into up to k arrays with length 2^i. Insertion into empty array with one element capacity is easy, insertion into array with single element creates an array with two elements. If you already have an array of two elements, you should merge these elements into array of 4 elements. The merge operation is fast and cache oblivious. Thus, insertion into a set of these arrays is fast. Query is not so fast - O(log^2N). But I can direct you to Cache-Oblivious Lookahead Arrays (COLA) paper where a technique to get back to O(logN) complexity for lookup is described. Or you can simple merge these arrays into one at the bulk insertion end. Source code (not mine): https://github.com/giannitedesco/cola https://github.com/giannitedesco/cola