This implementation is missing a lot of the usual tricks. By slicing a single array you only need O(1) not O(log n) overhead. This does of course means droppin

This implementation is missing a lot of the usual tricks. By slicing a single array you only need O(1) not O(log n) overhead. This does of course means dropping down to amortized insertion due to the occasional large reallocation (but if your OS supports `mremap` and your language allows you to use it, that goes away ... but the merge means you pay anyway). It never makes sense to allow a "null" array except for the smallest items (which I tend to put at the end, not the start). Also, if under N elements (16?) you should fall back to a linear search. Also worth noting that tombstones are a legitimate way of deleting elements. If your elements are (or contain, if structs, especially map-like entries) pointers you can just use a pointer to a private static variable (since you know nobody else can access it); if integers you can use the smallest integer except for the very first element of the array, which you can avoid turning into a tombstone. The trick is never to insert one at an intermediate level of the "tree", but instead bubble them down. (Bubbling down of self-invalidating elements like weak pointers is also quite possible, but turning all reads into potential writes complicates thread-safety if you care about that). You should also keep track of the number of deleted elements and perform a full re-sort if it exceeds the number of real elements or so. That said, there's enough branch-predictor overhead in this that you probably want to implement the delete-allowed version separately from the no-delete version. Sketch of the `get` code as I'm familiar with it: def get(array, elem, start, end): len = end - start chunk_size = round_down_to_power_of_2(len) while True: assert start + len == end if len < SMALL: # note that, after the first iteration, # len can be 0, 1, etc. even if chunk_size is still large return linear_search(array, elem, start, end) assert chunk_size <= len assert start + chunk_size <= end rv = binary_search(array, elem, start, start + chunk_size) if rv != NOT_FOUND: return rv start += chunk_size len -= chunk_size chunk_size /= 2