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 time and space, it seems that it does not work for arrays but linked lists. One key feature of the paper’s time algorithm is it can sort blocks of a list in time. For example, a list of elements are divided into blocks, each having elements. Now sorting the blocks according to the last element’s value needs to compare among k elements and moving blocks. That is or at most . Thus if , this is . However, swapping two blocks of size takes time as well. Thus the sorting of blocks does not work. In linked lists, however, just re-hooking the links and the swaping two blocks can be done in .

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