Lecture 6 - Standard, Efficient Merging Algorithm
5.2. Standard, Efficient Merging Algorithm
This version `clobbers' L1 and L2 but that's just for simplicity.
Don't implement it this way unless the specification says it's OK to
clobber L1 and L2.
- initialize L3 to be empty.
- Repeat the following until either L1 or L2 is empty (Note: we
only execute the loop body when both are non-empty):
- look at the heads of L1 and L2, determine which is
- Remove the smaller head from the list it is on and add it
at the end of L3.
- If L1 or L2 is non-empty (they cannot both be non-empty) then
join it to the end of L3.
Illustrate this merging algorithm on the example (from above): L1 =
[11,99] and L2 = [2,111,222]
- L3 = empty.
- Compare the heads of L1 and L2. 11 > 2 so we remove 2 from L2
and add it to the end of L3. Result: L1 = [11,99], L2 =
[111,222], L3 = .
- Compare the heads of L1 and L2. 11 < 111 so we remove 11 from
L1 and add it to the end of L3. Result: L1 = , L2 =
[111,222], L3 = [2,11].
- Compare the heads of L1 and L2. 99 < 222 so we remove 99 from
L1 and add it to the end of L3. Result: L1 =  (i.e. empty), L2
= [111,222], L3 = [2,11,99].
- L1 is empty but L2 is not, so we join L2 to L3. Result: L3 =
5.3. Special cases of the MERGE operation
There are two special cases of MERGE that we will need later.
INSERT a special case of MERGE
If L1 (or L2) is a singleton - a list with exactly one element (call
it E) - then MERGE(L1,L2,L3) has the same overall effect as
INSERT(E,L2,L3), and furthermore the algorithm behaves step-by-step
almost exactly like INSERT.
JOIN is a special case of MERGE
We've already seen an example where the result of JOINing two sorted
lists was sorted. What are the general conditions under which this
will happen? Let L1 and L2 be any sorted lists (in ascending order):
L1 = [A1,A2,...,An], L2 = [B1,B2,...,Bm].
When we join them we get: [A1,A2,...,An,B1,B2,...,Bm].
When will this result in a list that is sorted? What assumption(s)
do we have to make about the Ai and the Bi?
Answer: Everything in L1 must be smaller than
everything in L2.
How can we easily check this?
Answer: Compare An (the biggest in L1) to B1 (the
smallest in L2).