How do hierarchical XSL sorting?

Question

I have the following input XML:

<?xml version="1.0" encoding="UTF-8"?>
<soldiers>
    <soldier>
        <name>John</name>
        <supervisor>Marcus</supervisor>
    </soldier>
    <soldier>
        <name>Marcus</name>
        <supervisor>Mike</supervisor>
    </soldier>
    <soldier>
        <name>Frank</name>
        <supervisor>Marcus</supervisor>
    </soldier>
    <soldier>
        <name>Mike</name>
        <supervisor>Anna</supervisor>
    </soldier>
</soldiers>

Now I'm looking for a way sorting this XML hierarchicaly based on supervisor tag. What's the most performant way to do this? The result of the given example should look as following:

<?xml version="1.0" encoding="UTF-8"?>
<soldiers>
    <soldier>
        <name>Mike</name>
        <supervisor>Anna</supervisor>
    </soldier>
    <soldier>
        <name>Marcus</name>
        <supervisor>Mike</supervisor>
    </soldier>
    <soldier>
        <name>John</name>
        <supervisor>Marcus</supervisor>
    </soldier>
    <soldier>
        <name>Frank</name>
        <supervisor>Marcus</supervisor>
    </soldier>
</soldiers>

So Mike has no supervisor listed in here, hence he is on the top. Marcus' supervisor is Mike, hence he is under Mike. John's and Frank's supervisor is Marcus, hence they are at the very bottom.

Answer 1

You can use a key to follow the references:

<xsl:transform xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="2.0">

    <xsl:output indent="yes"/>

    <xsl:key name="ref" match="soldier" use="supervisor"/>

    <xsl:template match="soldiers">
        <xsl:copy>
            <xsl:apply-templates select="soldier[not(supervisor = ../soldier/name)]"/>
        </xsl:copy>
    </xsl:template>

    <xsl:template match="soldier">
        <xsl:copy-of select="."/>
        <xsl:apply-templates select="key('ref', name)"/>
    </xsl:template>
</xsl:transform>

Based on the comment of @michael.hor257k you might rather want

<xsl:transform xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="2.0"
    xmlns:mf="http://example.com/mf" exclude-result-prefixes="mf">

    <xsl:output indent="yes"/>
    <xsl:strip-space elements="*"/>

    <xsl:key name="ref" match="soldier" use="supervisor"/>

    <xsl:variable name="main-root" select="/"/>

    <xsl:function name="mf:refs" as="element(soldier)*">
        <xsl:param name="input" as="element(soldier)*"/>
        <xsl:copy-of select="$input"/>
        <xsl:sequence select="if (key('ref', $input/name, $main-root)) then mf:refs(key('ref', $input/name, $main-root)) else ()"/>
    </xsl:function>

    <xsl:template match="soldiers">
        <xsl:copy>
            <xsl:sequence select="mf:refs(soldier[not(supervisor = ../soldier/name)])"/>
        </xsl:copy>
    </xsl:template>

</xsl:transform>

which uses the same key but outputs each level completely first before recursing to the next level.