Another thing that works is a length-sqrt(n) list of length-sqrt(n) sorted lists with internal gaps, like with Python's SortedContainers[1]. Something like thi

Another thing that works is a length-sqrt(n) list of length-sqrt(n) sorted lists with internal gaps, like with Python's SortedContainers[1]. 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. So you'd store like this |----------HEADER---------| |-----------------------BUCKETS------------------------| idx (0, 3) (2, 2) (1, 4) (_, _) [1, 3, 7, _] [14, 15, 16, 19] [9, 12, _, _] [_, _, _, _] length Cache efficiency might also suggest you store the minimums of each list in the tuples. 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's O(log n). 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's amortized out. Deletion is even easier since you don'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). Creating the structure is trivially O(n log n), since it's sorted. Converting to a sorted list is just compacting the buckets. 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. For a cache-efficient design it's pretty neat. Binary searches are fast, after all. [1]: http://www.grantjenks.com/docs/sortedcontainers/implementation.html http://www.grantjenks.com/docs/sortedcontainers/implementati... [2]: When you split an overfull subarray, each new subarray will be half full.