Is it possible to apply xsl:sort on the output XML?
Yes, multipass processing is possible, and especially in XSLT 2.0 you don't even need to apply an xxx:node-set() extension on the result, because the infamous RTF type does no longer exist:
<xsl:stylesheet version="2.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output omit-xml-declaration="yes" indent="yes"/>
<xsl:template match="/">
<xsl:variable name="vPass1">
<!--
Put/Invoke your cirrent code here
to generate the following
-->
<Records>
<Record key="XX3">
</Record>
<Record key="XX2">
</Record>
<Record key="XX4">
</Record>
<Record key="XX1">
</Record>
</Records>
</xsl:variable>
<xsl:apply-templates select="$vPass1/*"/>
</xsl:template>
<xsl:template match="Records">
<Records>
<xsl:perform-sort select="*">
<xsl:sort select="@key"/>
</xsl:perform-sort>
</Records>
</xsl:template>
</xsl:stylesheet>
When this transformation is performed on any XML document (not used/ignored), the wanted, correct, sorted result is produced:
<Records>
<Record key="XX1"/>
<Record key="XX2"/>
<Record key="XX3"/>
<Record key="XX4"/>
</Records>
In XSLT 1.0 it is almost the same with the additional conversion of the result from RTF type to a normal tree:
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:ext="http://exslt.org/common"
exclude-result-prefixes="ext">
<xsl:output omit-xml-declaration="yes" indent="yes"/>
<xsl:template match="/">
<xsl:variable name="vrtfPass1">
<!--
Put/Invoke your cirrent code here
to generate the following
-->
<Records>
<Record key="XX3">
</Record>
<Record key="XX2">
</Record>
<Record key="XX4">
</Record>
<Record key="XX1">
</Record>
</Records>
</xsl:variable>
<xsl:variable name="vPass1"
select="ext:node-set($vrtfPass1)"/>
<xsl:apply-templates select="$vPass1/*"/>
</xsl:template>
<xsl:template match="Records">
<Records>
<xsl:for-each select="*">
<xsl:sort select="@key"/>
<xsl:copy-of select="."/>
</xsl:for-each>
</Records>
</xsl:template>
</xsl:stylesheet>