Посмотрите на CollectionView / CollectionViewSource классов. Эти классы располагаются «между» вашей ObservableCollection и логикой привязки данных WPF для выполнения таких операций, как сортировка, фильтрация и т. Д.
Я подозреваю, что написание ваших собственных функций сортировки из NotifyCollectionChanged является источником ваших проблем с производительностью; это зависит от вашей точной реализации, но, вероятно, при сортировке списка возникает множество событий CollectionChanged, что приводит к повторному связыванию WPF коллекции на каждой итерации подпрограммы сортировки ... которая будет невероятно медленной, поскольку вы описано.
CollectionView и CollectionViewSource не влияют на исходную коллекцию, а только на представление коллекции, отображаемое в пользовательском интерфейсе, поэтому вы должны увидеть значительное ускорение по сравнению с тем, что вы делаете сейчас. Когда был выпущен элемент управления Microsoft DataGrid , они продемонстрировали его, отображая и сортируя миллионы строк - и он использует именно эти классы для выполнения своих сортировок. Вы действительно не должны видеть проблем с производительностью на 500 строк.
Наконец, разница между CollectionView и CollectionViewSource заключается в том, где они предназначены для использования; CollectionView используется, когда вы работаете в C #, CollectionViewSource, когда вы делаете это из XAML. Возможно, вы также захотите взглянуть на эту статью для краткого обзора этих классов.