Merging sorted lists requires an algorithm that considers each element of each list and ensures they appear in the correct sequence in the new list.
The algorithms may be slightly different depending on the choice of data structure, but it basically works like this:
initialize pointer/index to first element of the 1st sorted list (first)
initialize pointer/index to first element of the 2nd sorted list (second)
while elements to consider in both list
if first > second then
move first to the new list
have first point/index the next element in the 1st list
else
move second to the new list
have second point/index the next element in the 2nd list
endif
endwhile
while more elements to consider in 1st list
move first to the new list
have first point/index the next element in the 1st list
endwhile
while more elements to consider in 2nd list
move second to the new list
have second point/index the next element in the 2nd list
endwhile
Lets trace the algorithm:
Consider the 1st list containing: 12 16 17 20 21 27
Consider the 2nd list containing: 9 10 11 12 19
We begin by making sure we have a pointer/index to the first element in each
list:
12 16 17 20 21 27
first
9 10 11 12 19
second
(empty)
newlist
Now the first loop begins, the following shows what happens after each cycle of
the loop:
First pass:
12 16 17 20 21 27
first
9 10 11 12 19
second
9
newlist
Second pass:
12 16 17 20 21 27
first
9 10 11 12 19
second
9 10
newlist
Third pass:
12 16 17 20 21 27
first
9 10 11 12 19
second
9 10 11
newlist
Forth pass: Note that since first and second elements were the same, the
else path was taken.
12 16 17 20 21 27
first
9 10 11 12 19
second
9 10 11 12
newlist
Fifth pass:
12 16 17 20 21 27
first
9 10 11 12 19
second
9 10 11 12 12
newlist
Sixth pass:
12 16 17 20 21 27
first
9 10 11 12 19
second
9 10 11 12 12 16
newlist
Seventh pass:
12 16 17 20 21 27
first
9 10 11 12 19
second
9 10 11 12 12 16 17
newlist
Eighth pass: Note that once this cycle is finished the while loop condition
no longer holds.
12 16 17 20 21 27
first
9 10 11 12 19 (empty)
second
9 10 11 12 12 16 17 19
newlist
Now the second loop is being traced:
1st pass:
12 16 17 20 21 27
first
9 10 11 12 19 (empty)
second
9 10 11 12 12 16 17 20
newlist
2nd pass:
12 16 17 20 21 27
first
9 10 11 12 19 (empty)
second
9 10 11 12 12 16 17 20 21
newlist
3rd pass:
12 16 17 20 21 27 (empty)
first
9 10 11 12 19 (empty)
second
9 10 11 12 12 16 17 20 21 27
newlist
Note that the 3rd loop will not execute. If you consider things carefully, you will notice that only one of the last two loops may execute under any circumstance. The first does not end, unless we reach the end of one of the two sorted lists being merged.