> >  the only way to improve
> >  this - to make it O(C+R) rather than O(C*R) - is to hand-code a 
> >sort-merge join.
> Since rows and categories are already sorted, this is 
> probably the best thing to do.

It occurred to me after writing that you don't need to use recursion for
this: you can do a sort on the merged node-sets and then use grouping to
find the rows in each category. In 2.0, given

<category name="A" start="10"/>
<category name="B" start="100"/>
<category name="C" start="1000"/>
<category name="D" start="10000"/>
<category name="E" start="100000"/>

<row value="842"/>
<row value="9725"/>
etc

you can do

<xsl:variable name="merged-and-sorted">
  <xsl:perform-sort select="category|row">
    <xsl:sort select="self::category/@start | self::row/@value"/>
  </
</

<xsl:for-each-group select="$merged-and-sorted"
group-starting-with="category">
  <xsl:for-each select="current-group()[self::row]">
    <xsl:copy>
      <xsl:attribute name="category" select="current-group()[1]/@name"/>
      <xsl:copy-of select="@*|node()"/>
    </xsl:copy>
  </
</

Michael Kay
http://www.saxonica.com/