Make your own free website on
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.

Illustrate this merging algorithm on the example (from above): L1 = [11,99] and L2 = [2,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).