Standard Merge Algorithm:

• initialize L3=[]
• Repeat while neither L1 nor L2 is empty:
  • compare the heads of L1 and L2
  • remove smaller head from its list and add to the end of L3
• if L1 or L2 is non-empty, join it do the end of L3

L1=[11,99] L2=[2,111,222] L3=[]

L1=[11,99] L2=[111,222] L3=[2]

L1=[99] L2=[111,222] L3=[2,11]

L1=[] L2=[111,222] L3=[2,11,99]

L1=[] L2=[] L3=[2,11,99,111,222]

INSERT as a special case of MERGE: MERGE([E],L) has the same overall effect as INSERT(E,L).

JOIN as a special case of MERGE: when is it the case that MERGE([A1,...,An], [B1,...,Bm]) yields [A1,...,An,B1,...,Bm].

Answer: when for all i,j Ai<Bj.

How to check this efficiently?

Answer: compare An with B1.