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",
}