5.1. Naive Merging Algorithm
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?
- 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.
To illustrate this algorithm consider the earlier example: L1 =
[11,99] and L2 = [2,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).
- 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].