Another thing that works is a length-sqrt(n) list of length-sqrt(n) sorted lists with internal gaps, like with Python&#x27;s SortedContainers[1].<p>Something like this with a contiguous allocation would probably require quite a lot of empty space - 100% reserve for each subarray by necessity[2] and 50% for the array as a whole, so 200% overhead at worst and probably 90% overhead on average. Alternatively you can heap allocate each subarray at the expense of slower operations, but resulting in a more typical 100% worst-case overhead.<p>So you&#x27;d store like this<p><pre><code>    |----------HEADER---------| |-----------------------BUCKETS------------------------|
     idx
    (0, 3) (2, 2) (1, 4) (_, _) [1, 3, 7, _] [14, 15, 16, 19] [9, 12, _, _] [_, _, _, _]
        length
</code></pre>
Cache efficiency might also suggest you store the minimums of each list in the tuples.<p>So to search for a value, you do a binary search over the header to find the wanted bucket and then over the bucket to find the value. That&#x27;s O(log n).<p>Insertion is O(sqrt n) since you need to find the bucket and then do a normal insertion into it. You might need to reallocate the whole thing (remember to increase bucket size!) but that&#x27;s amortized out.<p>Deletion is even easier since you don&#x27;t have to deal with overflow (although you might want to move empty buckets to the end or merge adjacent ones, maybe). O(sqrt n).<p>Creating the structure is trivially O(n log n), since it&#x27;s sorted.<p>Converting to a sorted list is just compacting the buckets.<p>You also get access by index at O(sqrt n) speed since you just need to traverse the counts in the header. Not perfect, but close.<p>For a cache-efficient design it&#x27;s pretty neat. Binary searches are fast, after all.<p>[1]: <a href="http:&#x2F;&#x2F;www.grantjenks.com&#x2F;docs&#x2F;sortedcontainers&#x2F;implementation.html" rel="nofollow">http:&#x2F;&#x2F;www.grantjenks.com&#x2F;docs&#x2F;sortedcontainers&#x2F;implementati...</a><p>[2]: When you split an overfull subarray, each new subarray will be half full.