Dimitre,

> Is this what you wished? I'm afraid it's performance seems to be no
> better than O(N*N), hope I'm wrong.

I altered it slightly to take advantage of Saxon's XSLT 1.1 support
(rather than use msxsl:node-set()). Here's the amended table (the
measurements might be a little off because of a different test
stylesheet, but the pattern is evident):

count   Tail Recursive      Not Tail Recursive  Divide And Conquer
10         388                    393               556
50         429                    396               631
100        451                    403               696
200        611                    418               876
500       2666                    654              1880
1000     12726                   2241              5588

So the non-tail-recursive template performs best on all counts.

Cheers,

Jeni

---
Jeni Tennison
http://www.jenitennison.com/


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list