Как я сортирую заметный набор?

OP Edit: поскольку многие правильно указали, что исходный ответ не возвращает одну и ту же коллекцию (изначально больше внимания уделялось сортировке словарной части Q). См. редактирование внизу, где я обращаюсь к сортировке наблюдаемой коллекции. Оригинал слева здесь как все еще получающий вверх голоса

Вы можете использовать linq как иллюстрирует метод doSort ниже. Быстрый фрагмент кода: производит

3:xey. 6:50 7:aaa

В качестве альтернативы вы можете использовать метод расширения самой коллекции

var sortedOC = _collection.OrderBy(i => i.Key);

private void doSort()
{
    ObservableCollection<Pair<ushort, string>> _collection = 
        new ObservableCollection<Pair<ushort, string>>();

    _collection.Add(new Pair<ushort,string>(7,"aaa"));
    _collection.Add(new Pair<ushort, string>(3, "xey"));
    _collection.Add(new Pair<ushort, string>(6, "fty"));

    var sortedOC = from item in _collection
                   orderby item.Key
                   select item;

    foreach (var i in sortedOC)
    {
        Debug.WriteLine(i);
    }

}

public class Pair<TKey, TValue>
{
    private TKey _key;

    public TKey Key
    {
        get { return _key; }
        set { _key = value; }
    }
    private TValue _value;

    public TValue Value
    {
        get { return _value; }
        set { _value = value; }
    }

    public Pair(TKey key, TValue value)
    {
        _key = key;
        _value = value;

    }

    public override string ToString()
    {
        return this.Key + ":" + this.Value;
    }
}

EDIT

Для возврата наблюдаемой коллекции, вызовите .ToObservableCollection по sortedOC, используя, например, эту реализацию.

OP EDIT. Сортировка наблюдаемого и возвращение одного и того же отсортированного объекта может быть выполнена методом расширения. Для больших коллекций следите за количеством уведомлений об изменении коллекции, например, об использовании

public static void Sort<T>(this ObservableCollection<T> observable) where T : IComparable<T>, IEquatable<T>
    {
        List<T> sorted = observable.OrderBy(x => x).ToList();

        int ptr = 0;
        while (ptr < sorted.Count)
        {
            if (!observable[ptr].Equals(sorted[ptr]))
            {
                T t = observable[ptr];
                observable.RemoveAt(ptr);
                observable.Insert(sorted.IndexOf(t), t);
            }
            else
            {
                ptr++;
            }
        }
    }

: Пример с наблюдателем (использовал класс Person для упрощения)

public class Person:IComparable<Person>,IEquatable<Person>
    { 
        public string Name { get; set; }
        public int Age { get; set; }

        public int CompareTo(Person other)
        {
            if (this.Age == other.Age) return 0;
            return this.Age.CompareTo(other.Age);
        }

        public override string ToString()
        {
            return Name + " aged " + Age;
        }

        public bool Equals(Person other)
        {
            if (this.Name.Equals(other.Name) && this.Age.Equals(other.Age)) return true;
            return false;
        }
    }

  static void Main(string[] args)
    {
        Console.WriteLine("adding items...");
        var observable = new ObservableCollection<Person>()
        {
            new Person { Name = "Katy", Age = 51 },
            new Person { Name = "Jack", Age = 12 },
            new Person { Name = "Bob",  Age = 13 },
            new Person { Name = "John", Age = 14 },
            new Person { Name = "Mary", Age = 41 },
            new Person { Name = "Jane", Age = 20 },
            new Person { Name = "Jim",  Age = 39 },
            new Person { Name = "Sue",  Age = 15 },
            new Person { Name = "Kim",  Age = 19 }
        };

        //what do observers see?
        observable.CollectionChanged += (o, e) => {

            if (e.OldItems != null)
            {
                foreach (var item in e.OldItems)
                {
                    Console.WriteLine("removed {0} at index {1}", item, e.OldStartingIndex);
                }
            }

            if (e.NewItems != null)
            {
                foreach (var item in e.NewItems)
                {
                    Console.WriteLine("added {0} at index {1}", item, e.NewStartingIndex);
                }
            }};            

        Console.WriteLine("\nsorting items...");
        observable.Sort();
    };

Вывод сверху:
. удалила Кэти в возрасте 51 года с индексом 0
. добавила Кэти в возрасте 51 года по индексу 8
. удалила Мэри в возрасте 41 года по индексу 3
. добавил Мэри в возрасте 41 года на индекс 7
. удалил Джейн в возрасте 20 лет по индексу 3
. добавил Джейн в возрасте 20 лет на индексе 5
. удалил Джима в возрасте 39 лет по индексу 3
. добавил Джима в возрасте 39 лет по индексу 6
. удалил Джейн в возрасте 20 лет по индексу 4
. добавлена Джейн в возрасте 20 лет при индексе 5

Класс Person реализует как IComparable, так и IEquatable. Последний используется для минимизации изменений в коллекции, чтобы уменьшить количество уведомлений об изменениях