Lecture 6 - Standard, Efficient Merging Algorithm

5.2. Standard, Efficient Merging Algorithm

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 smaller.
- 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.

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.

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 = [2].
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 = [99], 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 = [2,11,99,111,222].

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).