>Here comes the difficult part: How can I change the following style
>sheet to do the re-shuffling without touching the first three
>templates.
><xsl:template match="a">
>........
></xsl:template>
><xsl:template match="b">
>........
></xsl:template>
><xsl:template match="c">
>........
></xsl:template>
><xsl:template match="note">
>........
></xsl:template>

My idea would be to use modes. First, in the normal processing mode, you
want to disregard <note>, so you change the existing note template to

<xsl:template match="note" />

Then, you add a new template for note that actually does what you need
to do with note, but in a specific mode:

<xsl:template match="note" mode="noteprocessing">
  ........
</xsl:template>

Finally, you add a note-collecting apply-templates call to the template
for <root>:

<xsl:template match="root">
  ...
  <xsl:apply-templates /> <!-- just what you already have -->

  <!-- new: -->
  <xsl:apply-templates select="descendant::note" mode="noteprocessing" />
  ...
</xsl:template>

Mind that in any calls to apply-templates in the mode'd note template,
you should add mode="#default" to resume using the non-moded templates
for the note element contents.

-Christian