Lecture 6 - Naive Merging Algorithm

5.1. Naive Merging Algorithm

initialize L3 to be equal to L1 (a copy of L1).
for each element E in L2, INSERT E (a copy of E) into L3.

the INSERT operation takes an element E and a sorted list L and changes L so that it contains E (and is still sorted). The obvious insertion algorithm is to scan along L asking at each point, is this the right place to insert E?

To illustrate this algorithm consider the earlier example: L1 = [11,99] and L2 = [2,111,222].

L3 = [11,99]
INSERT 2 into L3. Compare 2 to 11; it's smaller so 2 goes before 11, i.e. at the very beginning of L3. Result: L3 = [2,11,99].
INSERT 111 into L3. Compare 111 to 2. It's bigger, so compare 111 to the next element. 111 > 11, so compare 111 to the next element. 111 > 99 and 99 is the last element in L3, so add 111 after 99. Result: L3 = [2,11,99,111].
INSERT 222 into L3. Compare 222 to 2. It's bigger so compare 222 to the next element. 222 > 11, so compare it to the next element. 222 > 99, so compare it to the next element. 222 > 111 and 111 is the last element, so add 222 after 111. Result: L3 = [2,11,99,111,222].

The drawback of this simple algorithm is that it is very inefficient. It does one INSERT operation for each element in L2 and each of these INSERT operations requires scanning the whole list built up so far. This is not the most efficient INSERT algorithm: because L2 is sorted, it is possible to find the correct place to insert a value with much less effort. But it cannot be speeded up enough to make this merging algorithm as fast as the following one, which exploits the fact that both lists are sorted (the naive merging algorithm works the same whether L1 is sorted or not).