Сортировка списка папок по вложенности

public class AnalyseObject
{
    public ObjectType Type { get; set; } //enum: диск / папка / файл
    public string Path { get;  set; } //содержит выше приведенные значения
    public bool IsAnalyzed { get ; set; } //true - анализировать, false - нет
}  

xmlns:scm="clr-namespace:System.ComponentModel;assembly=WindowsBase"
<CollectionViewSource x:Key="pathesVS" Source="{Binding Pathes}">
    <CollectionViewSource.SortDescriptions>
        <scm:SortDescription PropertyName="Path" />
    </CollectionViewSource.SortDescriptions>
</CollectionViewSource>  

Пошел по другому пути. Дополнил класс AnalyseObject:

public class AnalyseObject : IComparable<AnalyseObject>
{
    public ObjectType Type { get; set; } //enum: диск / папка / файл
    public string Path { get;  set; } //содержит выше приведенные значения
    public bool IsAnalyzed { get ; set; } //true - анализировать, false - нет
    public int CompareTo(AnalyseObject other)
    {
        if (this.Path == other.Path)
            return 0;
        int thisPathLength = this.Path.Length;
        int otherPathLength = other.Path.Length;
        int maxIndex = Math.Min(thisPathLength - 1, otherPathLength - 1);
        for (int i = 0; i <= maxIndex; i++)
        {
            if (this.Path[i] == other.Path[i]) continue;
            if (this.Path[i] == '\\') return -1;
            if (other.Path[i] == '\\') return 1;
            return this.Path[i] < other.Path[i] ? -1 : 1;
        }
        return thisPathLength < otherPathLength ? -1 : 1;
    }
}  

Добавил:

public static class ObservableCollection
{
    public static void Sort<TSource, TKey>(this ObservableCollection<TSource> source, Func<TSource, TKey> keySelector, bool byDescending = false)
    {
        if (!byDescending)
        {
            List<TSource> sortedList = source.OrderBy(keySelector).ToList();
            source.Clear();
            foreach (var sortedItem in sortedList)
            {
                source.Add(sortedItem);
            }
        }
        else
        {
            List<TSource> sortedList = source.OrderByDescending(keySelector).ToList();
            source.Clear();
            foreach (var sortedItem in sortedList)
            {
                source.Add(sortedItem);
            }
        }
    }
}

Сортировку провожу принудительно:

Pathes.Sort(p => p);

Наверно далеко не самый оптимальный вариант, но вроде работает как надо. Буду признателен если кто-то предложит вариант лучше.

В первом приближении я бы сделал как-то так:

Возьмем отсюда метод EnumerateParts и напишем на его основе компарер:

class PathComparer : IComparer<string>
{
    public int Compare(string x, string y)
    {
        var xParts = EnumerateParts(x).Reverse().ToList();
        var yParts = EnumerateParts(y).Reverse().ToList();
        for (int i = 0; i < xParts.Count && i < yParts.Count; ++i)
        {
            var c = string.Compare(xParts[i], yParts[i]);
            if (c != 0) return c;
        }
        return xParts.Count.CompareTo(yParts.Count);
    }
    IEnumerable<string> EnumerateParts(string path)
    {
        var root = Path.GetPathRoot(path);
        while (path != root)
        {
            yield return Path.GetFileName(path);
            path = Path.GetDirectoryName(path);
        }
        yield return root;
    }
}

Теперь можно пользоваться так:

var source = new[]
{
    @"C:\Program Files\Microsoft",
    @"C:\Program Files (x86)",
    @"C:\Program Files"
};
foreach (var p in source.OrderBy(s => s, new PathComparer()))
    Console.WriteLine(p);

Работает как надо, но если поставить брейкпоинт в EnumerateParts, то можно подсчитать, что для 3х строк он вызывается аж 10 раз, что может быть очень неэффективно, поэтому я бы переписал код так, чтобы EnumerateParts вызывался только один раз для каждой строки. Например:

class PathParts : IComparable<PathParts>
{
    readonly List<string> parts;
    public PathParts(string path)
    {
        parts = EnumerateParts(path).Reverse().ToList();
    }
    public int CompareTo(PathParts other)
    {
        for (int i = 0; i < parts.Count && i < other.parts.Count; ++i)
        {
            var c = string.Compare(parts[i], other.parts[i]);
            if (c != 0) return c;
        }
        return parts.Count.CompareTo(other.parts.Count);
    }
    IEnumerable<string> EnumerateParts(string path)
    {
        var root = Path.GetPathRoot(path);
        while (path != root)
        {
            yield return Path.GetFileName(path);
            path = Path.GetDirectoryName(path);
        }
        yield return root;
    }
}

и теперь:

var source = new[]
{
    @"C:\Program Files\Microsoft",
    @"C:\Program Files (x86)",
    @"C:\Program Files"
};
var ordered = source.Select(s => new { s, pp = new PathParts(s) })
                    .OrderBy(a => a.pp)
                    .Select(a => a.s);
foreach (var p in ordered)
    Console.WriteLine(p);

Ну и теперь можете сделать PathParts вложенным приватным классом в своем AnalyseObject, также создавать экземпляр PathParts один раз при создании и потом выставить метод:

public int CompareTo(AnalyseObject other) => pathParts.CompareTo(other.pathParts);

Я буду считать, что вы знаете как получить список директорий (см. вопросы типа такого), поэтому сосредоточусь только на построении linq-запроса, который отсортирует вашу коллекцию.

Мои тестовые данные будут такие:

private IEnumerable<string> GetDirectoriesStub()
{
    return new string[]
    {
         @"C:\Documents and Settings"
        ,@"C:\Program Files"
        ,@"C:\Program Files (x86)"
        ,@"C:\Users"
        ,@"C:\Windows"
        ,@"C:\git\gitlab.com"
        ,@"C:\Program Files\Common Files"
        ,@"C:\git\github.com"
        ,@"C:\Program Files\dotnet"
        ,@"C:\Program Files\Git"
        ,@"C:\Program Files\Git\bin"
        ,@"C:\Program Files\Git\dev\shm"
        ,@"C:\git"
        ,@"C:\Program Files\nodejs"
        ,@"C:\Program Files\Git\dev\mqueue"
    };
}   

В первую очередь я посчитаю в каждой строке количество символов \. Чем больше будет таких символов, тем глубже будет лежать папка, тем больше её level:

var paths = this.GetDirectoriesStub();
paths.Select(x => new { Path = x, Level = x.Count(y => y == '\\')} )
     .Dump();

Получаем следующий набор данных:

Теперь сортируем нужным нам образом. Судя по озвученнм условиям, надо во-первых отсортировать по уровню вложенности, а во-вторых — по имени папки:

paths.Select(x => new { Path = x, Level = x.Count(y => y == '\\') })
     .OrderBy(x => x.Level)
     .ThenBy(x => x.Path)
     .Dump();

Получается так:

Что-то некрасиво. Попробуем поменять сортировку: сначала по x.Path, потом по x.Level:

Кажется, так гораздо логичнее и понятнее.

Update

Очень близко, но не совсем то. Обратите внимание на "C:\Program Files (x86)", который расположен между "C:\Program Files" и "C:\Program Files\Common Files". А по логике он должен выводиться после всех вложенных в "C:\Program Files"

Вот тут уже возможно пора строить дерево, чтобы было видно, у какой папки какие дочерние. Но в принципе, можно извернуться и по-прежнему обойтись сортировкой.

Добавим немного магии с весовыми коэффициентами:

paths.Select(x => new { 
        Path = x, 
        PathForSorting = (x + '\x01').Replace('\\', '\x02'), 
        Level = x.Count(y => y == '\\') })
     .OrderBy(x => x.PathForSorting)
     .ThenBy(x => x.Path)
     .ThenBy(x => x.Level)
     .Dump();

В принципе, работает и если убрать .Replace('\\', '\x02') - но для надёжности оставил полный вариант. (В полном варианте можно будет ещё некоторые дополнительные условия учесть, если понадобится)

paths.Select(x => new { 
        Path = x, 
        PathForSorting = (x + '\x01'),//.Replace('\\', '\x02'), 
        Level = x.Count(y => y == '\\') })
     .OrderBy(x => x.PathForSorting)
     .ThenBy(x => x.Path)
     .ThenBy(x => x.Level)
     .Dump();

Пояснение магии. Зачем был введён первый символ? Чтобы гарантированно различать кто является родителем, а кто потомком. Если ранее достаточно было считать, что "у кого длина строки меньше - тот и выше в сортировке / иерархии", то с учётом примера уже нужно определять точнее.

Второй символ я ввёл исключительно для наглядности, выбрав его больше, чем символ1. Неявно правило сортировки "\x01 показывать выше \x02" звучит как "родительская папка (это у нас символ \x01) располагать выше любых вложенных в неё папок (это символ 2)". Это правило избыточно и введено только для наглядности, чтобы можно было вербализировать это правило (явное лучше неявного).

В целом, я считаю, что уже в этом месте количество применённой магии подходит уже к отметке, где пора думать над построением дерева.

Причин тут две.

Во-первых, некоторая неочевидность алгоритма (магия).

Во-вторых, вполне возможно, что у вас в именах директорий встретятся символы ниже пробельного (всякие кривые папки) и в реальном приложении лучше избегать таких хаков. Оно вам надо, чтобы пользователи программы предпочли другое ПО, которое не будет глючить даже в случае некорректных папок на диске? )