IComparabale sorts in unexpected order

Question

I'm sorry but I think I'll have to stick in a lot of code into my question. The good news is though, if you have the time, you can just copy this into a Console Application and execute it so you can see the issue with the results.

I have been given a list (and yes, the list in the code below actually is the list!). Essentially, I will be given List<string, string> which I will call List<ColLeft, ColRight> just for clarity.

ColLeft is already grouped and must remain grouped.

ColRight is not alphabetical and needs to be within its group.

I am on .NET 2.0 and as such I've implemented IComparable<T>. However, the list is returned out of order and I can't understand why (same issue persists run on VS2005 or VS2010).

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace SortingLists
{
    class Program
    {
        static void Main()
        {
            List<ListContents> listContents = ListContents.GetListContents();
            WriteOut(listContents);
            Console.WriteLine("\r\n");

            listContents.Sort();
            WriteOut(listContents);
            Console.ReadKey();
        }

        private static void WriteOut(List<ListContents> listContents)
        {
            foreach (ListContents content in listContents)
                Console.WriteLine(content.ColLeft + " --- " + content.ColRight);
        }
    }

    struct ListContents : IComparable<ListContents>
    {
    #region Constructor

    public ListContents(string l, string r)
    {
        this.ColLeft = l;
        this.ColRight = r;
    }

    #endregion

    #region Fields

    public string ColLeft;
    public string ColRight;

    #endregion

    #region IComparable<ListContents> Members

    public int CompareTo(ListContents other)
    {
        if (this.ColLeft.CompareTo(other.ColLeft) == -1)
            return this.ColLeft.CompareTo(other.ColLeft);
        else
            return this.ColRight.CompareTo(other.ColRight);
    }

    #endregion

    #region Methods

    public static List<ListContents> GetListContents()
    {
        List<ListContents> lcList = new List<ListContents>();
        lcList.Add(new ListContents("UFT", "a"));
        lcList.Add(new ListContents("UFT", "c"));
        lcList.Add(new ListContents("UFT", "b"));
        lcList.Add(new ListContents("RT", "f"));
        lcList.Add(new ListContents("RT", "e"));            
        lcList.Add(new ListContents("RT", "d"));
        lcList.Add(new ListContents("UT", "m"));
        lcList.Add(new ListContents("UT", "o"));
        lcList.Add(new ListContents("UT", "n"));            
        return lcList;
    }
}

I can solve it though - if I change the order of GetListContents() to something like...

    public static List<ListContents> GetListContents()
    {
        List<ListContents> lcList = new List<ListContents>();
        lcList.Add(new ListContents("UFT", "a"));
        lcList.Add(new ListContents("UFT", "c"));
        lcList.Add(new ListContents("UFT", "b"));
        lcList.Add(new ListContents("RT", "e"));
        lcList.Add(new ListContents("RT", "f"));//Moved this item
        lcList.Add(new ListContents("RT", "d"));
        lcList.Add(new ListContents("UT", "m"));
        lcList.Add(new ListContents("UT", "o"));
        lcList.Add(new ListContents("UT", "n"));            
        return lcList;
    }

...Then the results come out as desired. Obviously this isn't a fix as I can't predict what order the List will come in, the only constant is that ColLeft is grouped.

Can any one help me understand why this behaviour?

Answer 1

The list is returned out of order because you have not preserved the original order anywhere. In LINQ (.NET 3.x) you could do it as follows:

list.GroupBy(x => x.LeftCol)
    .Select(g => g.OrderBy(x => x.RightCol))
    .SelectMany(x => x)
    .ToList();

In .NET 2.0 you'd have to do something similar; i.e. first group by LeftCol, then sort each group by RightCol, then concatenate the groups.

For example, if you control the ListContents class, you could add a field or property int Index that represents the order you want to preserve (0 for the first group; 1 for the second group and so on). Then sort it using a comparer that compares first by Index, then by RightCol:

int index = 0;
for(int i=0; i<list.Count; i++)
{
    if (i > 0 && list[i].LeftCol != list[i - 1].LeftCol) index++;
    list[i].Index = index;
}

...

public int CompareTo(ListContents other)
{
    int result = this.Index.CompareTo(other.Index);
    if (result != 0) return result;
    return this.ColRight.CompareTo(other.ColRight);
}

If you don't want to modify the ListContents class, you could do something similar by wrapping each item in a Tuple<int, ListContents> before sorting.