Unstable linear time O(1) space merging
Steven L. Dvorak · The Computer Journal · 1988
In this paper a version of unstable merging of two neighbouring segments in an one-dimensional array is presented. The algorithm runs in O(1) space and in linear time. It is based on stable merging,1 but its working area is not chosen outside merged segments; instead it occupies the end of one of them. Despite the fact that there are no restrictions on segment sizes, the algorithm is the fastest in its class of those published so far.