Black-White Array: A New Data Structure for Dynamic Data Sets

This is interesting! Some thoughts:

• The API as presented doesn’t include ordered iteration, unlike tree-based structures. So hash tables are a valid competitor, and a good open hash implementation ought to have better performance … right?
• However I think ordered iteration can be done by traversing & merging the segments in parallel, in something like O(n log n) time.
• I wish they’d shown timings for competing data structures like RB-trees.
• There’s something about the merge algorithm that reminds me of the Towers of Hanoi…

Does the author skip the most interesting amortised complexity case? (The complexity of a mixed Insert/Delete sequence)