Editing Merge algorithm (section)

== Merging two lists ==

Merging two sorted lists into one can be done in [[linear time]] and linear or constant space (depending on the data access model). The following [[pseudocode]] demonstrates an algorithm that merges input lists (either [[linked list]]s or [[Array data structure|arrays]]) {{mvar|A}} and {{mvar|B}} into a new list {{mvar|C}}.<ref name="skiena">{{cite book |last=Skiena |first=Steven |author-link=Steven Skiena |title=The Algorithm Design Manual |publisher=[[Springer Science+Business Media]] |edition=2nd |year=2010 |isbn=978-1-849-96720-4 |page=123}}</ref>{{r|toolbox}}{{rp|104}} The function {{mono|head}} yields the first element of a list; "dropping" an element means removing it from its list, typically by incrementing a pointer or index.

 '''algorithm''' merge(A, B) '''is'''
     '''inputs''' A, B : list
     '''returns''' list
 
     C := new empty list
     '''while''' A is not empty and B is not empty '''do'''
         '''if''' head(A) ≤ head(B) '''then'''
             append head(A) to C
             drop the head of A
         '''else'''
             append head(B) to C
             drop the head of B
 
     ''// By now, either A or B is empty. It remains to empty the other input list.''
     '''while''' A is not empty '''do'''
         append head(A) to C
         drop the head of A
     '''while''' B is not empty '''do'''
         append head(B) to C
         drop the head of B
 
     '''return''' C

When the inputs are linked lists, this algorithm can be implemented to use only a constant amount of working space; the pointers in the lists' nodes can be reused for bookkeeping and for constructing the final merged list.

In the merge sort algorithm, this [[subroutine]] is typically used to merge two sub-arrays {{mono|A[lo..mid]}}, {{mono|A[mid+1..hi]}} of a single array {{mono|A}}. This can be done by copying the sub-arrays into a temporary array, then applying the merge algorithm above.{{r|skiena}} The allocation of a temporary array can be avoided, but at the expense of speed and programming ease. Various in-place merge algorithms have been devised,<ref>{{cite journal |last1=Katajainen |first1=Jyrki |first2=Tomi |last2=Pasanen |first3=Jukka |last3=Teuhola |title=Practical in-place mergesort |journal=Nordic J. Computing |volume=3 |issue=1 |year=1996 |pages=27–40 |citeseerx=10.1.1.22.8523}}</ref> sometimes sacrificing the linear-time bound to produce an {{math|''O''(''n'' log ''n'')}} algorithm;<ref>{{Cite conference| doi = 10.1007/978-3-540-30140-0_63| title = Stable Minimum Storage Merging by Symmetric Comparisons| conference = European Symp. Algorithms| volume = 3221| pages = 714–723| series = Lecture Notes in Computer Science| year = 2004| last1 = Kim | first1 = Pok-Son| last2 = Kutzner | first2 = Arne| isbn = 978-3-540-23025-0| citeseerx=10.1.1.102.4612}}</ref> see {{slink|Merge sort|Variants}} for discussion.