Report Number: CS-TR-77-625
Institution: Stanford University, Department of Computer Science
Title: A fast merging algorithm
Author: Brown, Mark R.
Author: Tarjan, Robert Endre
Date: August 1977
Abstract: We give an algorithm which merges sorted lists represented as balanced binary trees. If the lists have lengths m and n (m $\leq$ n), then the merging procedure runs in O(m log n/m) steps, which is the same order as the lower bound on all comparison-based algorithms for this problem.
http://i.stanford.edu/pub/cstr/reports/cs/tr/77/625/CS-TR-77-625.pdf