Алгоритм сортировки иерархических данных по алфавиту с учетом вложенности

Эта заметка будет интересна людям, которым приходиться работать с классификатором адресов Российской Федерации, сокращенно КЛАДР (подробнее...).

В КЛАДР у каждого адресного объекта есть уникальный код, в котором помимо прочего хранится информация о положении объекта во всей иерархии адресных объектов.

Код представляет набор цифр, разбитых на разряды.

Встала задача представить данные из КЛАДР в следующем виде:

Т.е. вывести их в отчет по алфавиту, сохраняя порядок вложенности в иерархии адресных объектов.

Был создан класс, описывающий сущность, выводимую в отчет:

public class AddressObjectGraph : IComparable
в этом классе был объявлен метод ToSortString:
        public string ToSortString()
        {
            // пробелы и запятые нужны лишь для наглядности,
            // в Release версии их можно убрать
            string sortFullName = string.Format(
                "{0}, {1}, {2}, {3}, {4}, {5}",
                RegionName + " " + RegionCode,
                AreaName + " " + AreaCode,
                CityName + " " + CityCode,
                PlaceName + " " + PlaceCode,
                StreetName + " " + StreetCode,
                HouseName + " " + HouseCode
            );
            return Regex.Replace(sortFullName, @"\s+", " ", RegexOptions.None);            
        }

Этот метод будет выводить информацию об объекте в следующем виде:
Тверская обл 69, Зубцовский р-н 010, 000, Борки д 036, Молодежная ул 0001, 0000

Также реализуем метод CompareTo:

        public int CompareTo(object obj)
        {
            var aoGraph = (AddressObjectGraph) obj;
            return this.ToSortString().CompareTo(aoGraph.ToSortString());
        }

Чтобы получить требуемый результат, у коллекции экземпляров типа AddressObjectGraph вызываем метод Sort, например:

var result = addressObjectGraphs.Sort();

Преобразование результирующей коллекции в требуемому виду - дело техники.