As David suggests, I think I'd go for the approach of generating a
stylesheet. In effect your <REPORT_FORMAT> element defines a miniature
programming language, and a good way of implementing such languages is
often to translate them to XSLT. I've done similar things with report
specifications entered interactively on the screen. You're already
doing dynamic construction/evaluation of XPath expressions, so dynamic
construction of the entire stylesheet (or of the controlling
framework, it can always include/import a fixed module) isn't a major
step from that.

I don't have the code to generate the stylesheet, but I'd like to
propose what I imagine the result should look like.

There is a string representation of the sorting order, captured in the
xsl:variable $order. Then there is one generated matching template for
each value of $order that may occur in reality. (Well, I didn't write
the code to generate these templates, so I hand-coded one and left the
rest up to imagination.) And there is a template to format the output
(the copy template). Auto-generated stuff should go in one module,
hand-coded stuff in the other one.

mludwig@forelle:~/Werkstatt/xsl > expand -t2 Sapir-2008-05-22.xsl
<xsl:transform version="2.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:import href="Sapir-sorting.xsl"/>
  <xsl:template match="REPORT">
    <xsl:copy>
      <ORDER-USED><xsl:value-of select="$order"/></ORDER-USED>
      <xsl:apply-templates select="*"/>
    </xsl:copy>
  </xsl:template>
</xsl:transform>

mludwig@forelle:~/Werkstatt/xsl > expand -t2 Sapir-sorting.xsl
<xsl:transform version="2.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <!-- Generate this module to include all needed permutations
  of your sort parameters. Hopefully, not too many! -->
  <!-- sorting criteria identifier; normalize by eliminating spaces -->
  <xsl:variable name="order"
    select="translate(/REPORT/REPORT_FORMAT/ORDER_BY, ' ', '')"/>
  <!-- just the copy template to generate output -->
  <xsl:template match="@*|node()">
    <xsl:copy>
      <xsl:apply-templates select="@*|node()"/>
    </xsl:copy>
  </xsl:template>
  <!-- sorting templates; should be generated -->
  <xsl:template match="X[ $order = 'DATE,ID_1,ID_2,TYPE' ]">
    <xsl:copy>
      <xsl:apply-templates select="X_ROW">
        <xsl:sort select="DATE"/>
        <xsl:sort select="ID_1"/>
        <xsl:sort select="ID_2"/>
        <xsl:sort select="TYPE"/>
      </xsl:apply-templates>
    </xsl:copy>
  </xsl:template>
  <!-- more of these -->
</xsl:transform>

mludwig@forelle:~/Werkstatt/xsl > expand -t2 Sapir-2008-05-22.xml
<REPORT>
  <REPORT_HDR>...</REPORT_HDR>
  <REPORT_FORMAT>
    <ORDER_BY>DATE, ID_1, ID_2, TYPE</ORDER_BY>
    <PARENT_NODE>X</PARENT_NODE>
    <CHILD_NODE>X_ROW</CHILD_NODE>
  </REPORT_FORMAT>
  <X>
    <X_ROW>
      <DATE>2008-05-25</DATE>
      <ID_1>14</ID_1>
      <TYPE>A</TYPE>
    </X_ROW>
    <X_ROW>
      <DATE>2008-05-19</DATE>
      <ID_1>3</ID_1>
      <TYPE>B</TYPE>
    </X_ROW>
    <X_ROW>
      <DATE>2008-05-29</DATE>
      <ID_1>2</ID_1>
      <TYPE>A</TYPE>
    </X_ROW>
    <X_ROW>
      <DATE>2008-05-22</DATE>
      <ID_1>6</ID_1>
      <TYPE>C</TYPE>
    </X_ROW>
  </X>
</REPORT>