How to sort a DataGrid using stable sorting?

Question

I've got a WPF DataGrid, and I've got it so that you can sort it by clicking on the column headers. It works, but it's unstable. How do I make it do stable sorting?

By this I mean, if I have this table:

Class    | Student    | Grade
-----------------------------
Art      | James      |  A
Art      | Amy        |  B
Art      | Charlie    |  A
Science  | James      |  D
Science  | Amy        |  A
Science  | Charlie    |  C
History  | James      |  B
History  | Amy        |  A
History  | Charlie    |  C

If I sort by student, it works like you'd expect:

Class    | Student    | Grade
-----------------------------
Art      | Amy        |  B
Science  | Amy        |  A
History  | Amy        |  A
Art      | Charlie    |  A
Science  | Charlie    |  C
History  | Charlie    |  C
Art      | James      |  A
Science  | James      |  D
History  | James      |  B

But if I now sort by class:

Class    | Student    | Grade
-----------------------------
Art      | James      |  A
Art      | Amy        |  B
Art      | Charlie    |  A
History  | James      |  B
History  | Amy        |  A
History  | Charlie    |  C
Science  | James      |  D
Science  | Amy        |  A
Science  | Charlie    |  C

It's destroyed the sort order of the students (unstable sorting). What I want is stable sorting, where it preserves the order:

Class    | Student    | Grade
-----------------------------
Art      | Amy        |  B
Art      | Charlie    |  A
Art      | James      |  A
History  | Amy        |  A
History  | Charlie    |  C
History  | James      |  B
Science  | Amy        |  A
Science  | Charlie    |  C
Science  | James      |  D

Seems like it should work like this by default, or at least be a toggle. Does anyone have any suggestions? @Eirik's idea of shift-clicking works, and that shows that the behaviour is present. However, what I'd really like is for to work like that without any modifiers. It shouldn't be a cause of "sort by this, then this, then this", it should be case of swapping the algorithm for a different one.

See this: http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

Answer 1

You should be able to sort by multiple columns by holding down shift when clicking on the columns. Try clicking on the class column then hold down shift and click on the student column.

Here's a solution for adding sorting in code behind:

private void myDataGridPreviewMouseDown(object sender, MouseButtonEventArgs e)
{
    DependencyObject dep = (DependencyObject)e.OriginalSource;

    while ((dep != null) && !(dep is DataGridColumnHeader))
    {
        dep = VisualTreeHelper.GetParent(dep);
    }

    if (dep == null)
        return;

    if (dep is DataGridColumnHeader)
    {
        DataGridColumnHeader columnHeader = dep as DataGridColumnHeader;

        ICollectionView view = CollectionViewSource.GetDefaultView((sender as DataGrid).ItemsSource);

        if (columnHeader.Content.Equals("Class") || columnHeader.Content.Equals("Student"))
        {
            view.SortDescriptions.Clear();
            view.SortDescriptions.Add(new SortDescription("Class", ListSortDirection.Ascending));
            view.SortDescriptions.Add(new SortDescription("Student", ListSortDirection.Ascending));
        }
    }
}

For this to work you have to disable the standard sorting. One way to do this is to stop the Sorting event, like so:

private void myDataGridSorting(object sender, DataGridSortingEventArgs e)
{
    e.Handled = true;
}

Edit: After reading hbarck's comment I read your question again, and it seems I missed some parts. If you change this code:

if (columnHeader.Content.Equals("Class") || columnHeader.Content.Equals("Student"))
{
    view.SortDescriptions.Clear();
    view.SortDescriptions.Add(new SortDescription("Class", ListSortDirection.Ascending));
    view.SortDescriptions.Add(new SortDescription("Student", ListSortDirection.Ascending));
}

to this:

if (Keyboard.IsKeyDown(Key.LeftCtrl) || Keyboard.IsKeyDown(Key.RightCtrl))
{
    view.SortDescriptions.Clear();
}

view.SortDescriptions.Insert(0, new SortDescription(columnHeader.Content.ToString(), ListSortDirection.Ascending));

you will have stable sorting. Click on Student to sort by Student, then click on Class to sort by Class, Student. If you hold down ctrl when clicking you clear previous sorting before sorting by the column that was clicked.

Answer 2

I've managed to get a stable sorting using a custom Comparer, but it kinda feels like a big hack...

I use ListCollectionView's CustomSort property to set my custom Comparer, which needs me to pass the collection to it when instantiating it.

private void Sorting(IEnumerable collection)
{
    var view = CollectionViewSource.GetDefaultView(collection) as ListCollectionView;

    if (view != null)
    {
        view.CustomSort = new StableComparer(collection);
    }
}

In my custom Comparer, I use the collection during the Compare method just to fallback to the items indexes when the regular comparison returns a zero (they are the same or have the same value).

public class StableComparer : IComparer
{
    public IEnumerable Collection { get; set; }

    public StableComparer(IEnumerable collection)
    {
        Collection = collection;
    }

    public int Compare(object x, object y)
    {
        IComparable x_Comparable = x as IComparable;
        IComparable y_Comparable = y as IComparable;

        if (x_Comparable != null && y_Comparable != null)
        {
            var comparison = x_Comparable.CompareTo(y_Comparable);

            // A zero value means x and y are equivalent for sorting, and they could
            //  be rearranged by an unstable sorting algorithm
            if (comparison == 0 && Collection != null)
            {
                // IndexOf is an extension method for IEnumerable (not included)
                var x_Index = Collection.IndexOf(x);
                var y_Index = Collection.IndexOf(y);

                // By comparing their indexes in the original collection, we get to
                //  preserve their relative order
                if (x_Index != -1 && y_Index != -1)
                    comparison = x_Index.CompareTo(y_Index);
            }

            return comparison;
        }

        return 0;
    }
}

I'm still testing this, so I can't guarantee this would work all the time... One problem would be keeping the Collection property inside the Comparer updated, for instance. Or supporting two sort directions (working on it now, shouldn't be difficult). Or checking how this works, performance-wise.

But I think the idea is clear; though hacky, like I said.