Content deleted Content added
|
|
|
# do something with the data items p<sub>0..n</sub> point to in their respective lists
# find out which of those pointers points to the item with the lowest key; advance one of those pointers to the next item in its list
==Pseudocode==
A simple non-recursive pseudocode implementation of merge with two lists might be written as follows:
'''function''' merge(a, b)
'''var''' ''list'' result
'''var''' ''int'' i, j := 0
'''while''' (i < length(a)) '''and''' (j < length(b))
'''if''' a[i] = b[j]
add a[i] to result // In case list a and b are identical, each holding only
// one element, say x, this algorithm would output the list
// consisting of a single x instead of the list holding two
// x's which is at least counter-intuitive.
i := i + 1
j := j + 1
'''else if''' a[i] < b[j]
add a[i] to result
i := i + 1
'''else'''
add b[j] to result
j := j + 1
'''while''' i < length(a)
add a[i] to result
i := i + 1
'''while''' j < length(b)
add b[j] to result
j := j + 1
'''return''' result
==Analysis==
|
