.NET Fiddle

CSharp · Console

/Program.cs

using System;
using System.Linq;
using System.Xml.Linq;

class Program
{
    public static void Main()
    {
        const string xml = @"
<Root>
    <I aa=""1"">
        <s aa=""3""/>
        <s aa=""1""/>
        <s aa=""2""/>
    </I>
    <I aa=""5"">
        <s aa=""3""/>
        <s aa=""1""/>
        <s aa=""2""/>
    </I>
    <I aa=""3"">
        <s aa=""3""/>
        <s aa=""1""/>
        <s aa=""2""/>
    </I>
    <I aa=""4"">
        <s aa=""3""/>
        <s aa=""1""/>
        <s aa=""2""/>
    </I>
</Root>";

        var root = XElement.Parse(xml);

        var newRoot = CopyAndSort(root);

        Console.WriteLine(newRoot);
    }

    private static XElement CopyAndSort(XElement e)
    {
        var elements = e.Elements()
            .OrderBy(x => (string)x.Attribute("aa"))
            .Select(CopyAndSort);
        return new XElement(e.Name, e.Attributes(), elements);
    }
}