Я не знаком ни с каким методом, кроме использования XSLT для сортировки XML.
Почему XSLT не вариант? Это просто и не должно быть нарушителем производительности. Вы можете кэшировать объект FreeThreadedDOMDocument после загрузки документа XSLT, чтобы избежать разбора и компиляции документа XSLT каждый раз.