The XQuery spec describes the semantics of sorting in terms of a stream of
  tuples - that is, it requires data structures outside the scope of the
  XPath/XQuery/XSLT data model. If it had been possible to describe the
  semantics without straying outside the data model, I think someone would
  have found a way of doing so. And if it requires extensions to the data
  model, then I suspect that mechanical translation into XSLT is quite
  difficult.

we'll see:-)

  Am I right in thinking that your translation models the stream of N tuples
  of width M as a sequence of length N*M, and then computes the sort key of
  each item in a way that ensures that all the M items corresponding to a
  single tuple get the same sort key, and therefore remain together when
  sorted?

Not really. It models it as a sequence of integers of length M*N and
calculates the sort key (and data needed for the result) by calculating
the equivalent indexes into the original sequences using mod and idiv.

given the general 2 variable case:


for $i in $is,  $j in $js
order by f($i,$j)
return
g($i,$j)

for some functions f and g then I think you can always replace this by

let $ci :=count($is) return
let $cj :=count($js) return
for $n in (0 to $ci * $cj)
let $i :=$is[$n  mod $ci)+1]
let $j := $js[($n idiv $ci) +1]
order by f($i, $j)
return
g($i,$j)

and once you have just a single for and order by, converting that to xsl
for-each and sort is just syntax.

David



________________________________________________________________________
This e-mail has been scanned for all viruses by Star. The
service is powered by MessageLabs. For more information on a proactive
anti-virus service working around the clock, around the globe, visit:
http://www.star.net.uk
________________________________________________________________________