Make your own free website on Tripod.com

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?

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).