
4.2.5.4 Efficiency issues There are many other nontrivial examples of this technique. However, often it turns out to be not the most efficient one, since it is quite easy to build inefficient rules and patterns. For instance, our first example with list sorting has a terrible performance and is completely impractical for any realistic sizes of a list, since the patternmatcher needs roughly linear (in the list size) time to find a first match for exchange, and then it only does a single exchange and starts all over! The number of exchanges needed is of the order of the square of the list size, and thus we conclude that our realization has roughly cubic complexity. Let us do some performance measurements:
This is the rule we need :
These timing results confirm our expectations. While this shows that our rule  based realization is completely inefficient since it adds another power of the list size to the standard complexity of the exchange sort algorithm, it is a good news that we can understand why this happens. Because it turns out that in many cases, the structures on which patterns are tried plus patterns themselves can be organized in such a way that the pattern is usually matched very soon after the beginning. In fact, as was demonstrated for instance by David Wagner in his book [7] in the context of the mergesort algorithm, this technique allows to make the rulebased solution the most efficient of all. So, to put it simple: organize your data such as to ensure that the pattern matcher wastes as little time on apriory doomed matching attempts as possible, and you will get an efficient rulebased solution.

