Wow! I independently came up with this algorithm a few years ago and wasn't even sure what to search for to find the prior art. Happy to see someone finally gave it a name and attempted to find the history.
Fun fact #1 that I also realized, which I have yet to see mentioned elsewhere (though people have almost surely realized this in various contexts):
This is not limited to binary search or mergesort.
This is a very general-purpose meta-algorithm for turning any batch algorithm into a streaming one. (!)
The merge() step is basically "redo computation on a batch 2x the size". You pay a log(n) cost for this ability. You can combine the batches in any way you want there. Here it happens to be a merge of two sorted arrays. But you can imagine this being anything, like "train your ML model again on the larger batch".
Fun fact #2: I believe you can add deletion support as well. This can be done with a hierarchical bitmap to help you quickly search for occupied slots. It comes at the cost of another log(n) factor in some operations. I have yet to search if there is a name for the hierarchical bitmap structure I have in mind, so I'm just calling it that for now.
For deletion, I think you can augment the current data structure so that instead of just storing each value, you pair it up with a Boolean telling whether the value is actually still included or not.
But you lose out on insertion and search efficiency; the worst case is dependent on the maximum number of values ever inserted, not the number of currently valid values.
Comments
Wow! I independently came up with this algorithm a few years ago and wasn't even sure what to search for to find the prior art. Happy to see someone finally gave it a name and attempted to find the history.
Fun fact #1 that I also realized, which I have yet to see mentioned elsewhere (though people have almost surely realized this in various contexts):
This is not limited to binary search or mergesort.
This is a very general-purpose meta-algorithm for turning any batch algorithm into a streaming one. (!)
The merge() step is basically "redo computation on a batch 2x the size". You pay a log(n) cost for this ability. You can combine the batches in any way you want there. Here it happens to be a merge of two sorted arrays. But you can imagine this being anything, like "train your ML model again on the larger batch".
Fun fact #2: I believe you can add deletion support as well. This can be done with a hierarchical bitmap to help you quickly search for occupied slots. It comes at the cost of another log(n) factor in some operations. I have yet to search if there is a name for the hierarchical bitmap structure I have in mind, so I'm just calling it that for now.
I think the term you're looking for is "Bentley-Saxe dynamisation" https://www.sciencedirect.com/science/article/abs/pii/019667...
Wow, thank you. Were you already aware of the name? Or if not, how did you search for it?
The technique was part of the functional programming pop culture 10-20 years ago.
For deletion, I think you can augment the current data structure so that instead of just storing each value, you pair it up with a Boolean telling whether the value is actually still included or not.
But you lose out on insertion and search efficiency; the worst case is dependent on the maximum number of values ever inserted, not the number of currently valid values.
The reason I mentioned using a hierarchical bitmap was precisely the inefficiency of just having one bool per element.