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