Stable Linear Time Sublinear Space Merging
Steven L. Dvorak · The Computer Journal · 1987
A new method for stable merging of two segments A(1..m), A(m+1..n) into A(1..n) in O(n) time is presented. There are no restrictions on n or m and the algorithm requires O(n1/2) workspace. The corresponding procedure is given in Pascal together with results of time measurements on samples of random integers.