Huang & Langston (1988) Practical In-Place Merging

A paper I read because of a mention in StackOverflow about merging two sorted arrays. However, despite it claims that it can merge two lists in \(O(n)\) time and \(O(1)\) space, it seems that it does not work for arrays but linked lists. One key feature of the paper’s \(O(n)\) time algorithm is it can sort blocks of a list in \(O(n)\) time. For example, a list of \(n\) elements are divided into \(k\) blocks, each having \(n/k\) elements. Now sorting the blocks according to the last element’s value needs to compare among k elements and moving \(k\) blocks. That is \(O(k \log k)\) or at most \(O(k^2)\). Thus if \(k=\sqrt{n}\), this is \(O(n)\). However, swapping two blocks of size \(n/k\) takes \(O(n/k)\) time as well. Thus the \(O(n)\) sorting of blocks does not work. In linked lists, however, just re-hooking the links and the swaping two blocks can be done in \(O(1)\).

Bibliographic data

@article{
   title = "Practical In-Place Merging",
   author = "Bing-Chao Huang and Michael A. Langston",
   journal = "Communications of the ACM",
   volume = "31",
   number = "3",
   pages = "348--352",
   month = "Mar",
   year = "1988",
}