is JOIN safe?

L1=[11,99] L2=[2,111,222] when JOINed the result is not sorted. JOIN is not safe.

There is a unique safe way to combine 2 sorted lists:

MERGE

Inputs: L1, L2
Output: L3
Preconditions: L1 and L2 are sorted
Postconditions: L3 is sorted and contains all the elements of L1 and L2 and no other.

Naive Merge Algorithm: initialize L3 to be a copy of L1, then for each element E in L2, INSERT E into L3.

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

L3=[11,99] INSERT(2,L3)

L3=[2,11,99] INSERT(111,L3)

L3=[2,11,99,111] INSERT(222,L3)

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

Very inefficient. Does not exploit the fact that both lists are sorted.