How to sort a C# List

I have used the Sort() method on List many times, but never dug vary deep into the functionality before. So, I through it was time to dig a bit deeper into the sorting functionality now. In this blog post I will go through the sorting functionality, from the simplest way to do a sort to a bit more advanced things like sorting on different fields then the a class creator was original designed for. At the end I will also look at sort speed perspective of the sorting, which could be interesting when you have larger amount of values you need to sort.

Sort list with primitive data types

Now it’s time to look at the first simple example of sorting a List.

namespace SortListExample
{
    class Program
    {
        static void Main(string[] args)
        {
            List<string> simpleList = new List<string>(new string[] {"1", "3", "2"});

            simpleList.Sort();

            foreach (string listItem in simpleList)
            {
                Console.WriteLine(listItem);
            }
        }
    }
}

In the Main method I first create a simpleList that will contain items of the data type string. Then I fill that list with 3 unordered items “1, 3, 2”.

Then I execute the Sort method on the simpelList. Now the simpleList has been sorted.

To prove that the list has been sorted, I’m using the foreach loop to iterate through simpleList and then print the values in the list to the console.

The printout on the screen looks like this:
1
2
3

So, this proves that simpleList has been sorted correctly with the Sort method.

The simpleList.Sort() method used is using the method Array.Sort and that method is implemented with the QuickSort algorithm to do the sort. The implementation is an unstable sort, which means if two items are equal the original order might not be preserved.

Specifying the sort order

The code example here shows that I first sort the list and then revers the sorted list:

simpleList.Sort();
simpleList.Reverse();

This is the simplest way, but it’s not likely the most efficient way of doing a descending sort order. If you just have a short list, the Reverse solution is probably good enough. If you have a larger amount of items in your list it’s probably better to use Linq to do the descending sort of your list.

This example shows how to do a descending sort of list with Linq:

private void SimpleSortOrderByDescending()
{
    List<string> simpleList = new List<string>(new string[] {"1", "3", "2"});
    List<string> simpleListResult = simpleList.OrderByDescending(item => item).ToList();

    foreach (string listItem in simpleList)
    {
        Console.WriteLine(listItem);
    }
}           

The Linq command for doing a descending sort on a list is OrderByDescending. In the earlier examples the list that we sorted changed its sort order when we executed the command Sort on it. But when we are using Linq to sort the list itself is not updated, instead it’s returning the sorted list and the original list is not modified.

Sort list with a custom data type

Now we have looked at how easy it is to sort a list that contains items of a primitive type. But if your list contains of items that is of a custom type items, which has several fields that you have created. How can you do a sort of your custom type?

I will use a simple Employee class to illustrate how you can add sort functionality to that class.

public class Employee
{
    public int EmployeeID { get; set; }
    public string EmployeeName { get; set; }

    public Employee(int EmployeeID, string EmployeeName)
    {
        this.EmployeeID = EmployeeID;
        this.EmployeeName = EmployeeName;
    }
}                 

This class has two fields, EmployeeID and EmployeeName, when the class looks like this; it’s not possible to sort a list with this class. The reason why it does not work to use the Sort method is that it does not know how to compare to Employee objects. This can be fixed, by letting the Employee class implement the IComparable interface. The Employee class will look like this when it is implementing the IComparable interface.

public class Employee : IComparable<Employee>
{
    public int EmployeeID { get; set; }
    public string EmployeeName { get; set; }

    public Employee(int EmployeeID, string EmployeeName)
    {
        this.EmployeeID = EmployeeID;
        this.EmployeeName = EmployeeName;
    }
    public int CompareTo(Employee other)
    {
        return this.EmployeeID.CompareTo(other.EmployeeID);
    }

}                 

When a class has implemented the IComparable interface it has to have the CompareTo method. It’s in this class you have to decide how to compare two Employees. In this case I’m just comparing the two EmployeeID:s to decide what Employee comes first.

Now the Employee class is prepared to being sorted. But how do you sort a list of Employee’s? It’s actually as simple as the earlier examples that I have shown, you just use the Sort method of the list of employees.

private static void SimpleSortEmployee()
{
    List<Employee> employeeList = new List<Employee>();
    employeeList.Add(new Employee(1, "Roger"));
    employeeList.Add(new Employee(3, "Anders"));
    employeeList.Add(new Employee(2, "Erika"));

    employeeList.Sort(); //This is sorting on EmployeeID

    foreach (Employee employeeItem in employeeList)
    {
        Console.WriteLine(employeeItem.EmployeeID + ". "  + employeeItem.EmployeeName);
    }
}                 

The list of employees are now sorted in a ascending way considering only the EmployeeID number.

Sort with different fields

We just looked at how we can sort a custom class based on the EmployeeID. But if you did not create the Employee class and could not change it. Is it then possible to do a sort on the EmployeeName? Yes there are ways to change what field the sort should be performed on even if you cannot modify the Employee class. One of the solutions could be to use a delegate to do the sort of the EmployeeName in the Employee class.

The code for that could look like this:

private static void SimpleSortEmployee()
{
    List<Employee> employeeList = new List<Employee>();
    employeeList.Add(new Employee(1, "Roger"));
    employeeList.Add(new Employee(3, "Anders"));
    employeeList.Add(new Employee(2, "Erika"));

    // Sort with delegate
    employeeList.Sort(delegate(Employee employee1, Employee employee2) { 
                 return employee1.EmployeeName.CompareTo(employee2.EmployeeName); });

    foreach (Employee employeeItem in employeeList)
    {
        Console.WriteLine(employeeItem.EmployeeID + ". "  + employeeItem.EmployeeName);
    }
}

It’s actually exactly the same code as the earlier example except that I added delegate to the Sort method. The delegate replaces the CompareTo method in the Employee class with the delegate in the Sort method call and the delegate dose the CompareTo with the EmployeeName instead on the original CompareTo method how did it with CompareID. So, now we have switched on what field the Sort is done on from EmployeeID to EmployeeName without modifying the Employee class.

There is also a short and maybe easier to read syntax for how to create your custom sort from outside of the Employee class. So you can use a lambda expression instead of the delegate in the as parameter to the Sort method. An implementation of the Sort method with lambda expression could look like this:

employeeList.Sort((employee1, employee2) => 
                   employee1.EmployeeName.CompareTo(employee2.EmployeeName));
             

Speed

Now we have looked at some common ways to sort lists in C#. Another interesting aspect of sorting is of course how long time it takes to sort a list. Different ways of doing the sort, takes different amount of time to perform. To make it even more complicated you also need to know how long the list is, to be able to decide what method you should use for your list. The only way of really knowing how you should do your sorting is to measure the different options with the real data that you are going to have in your list.

But to be able to give you some indications on how long time different long lists takes to sort with some different sorting methods, I have done some examples for you. I have done tests on 3 lists, one with 10 items, one with 1000 items and one with 1000000 items.

The items in the list that I have used looks like this:

"1", "3", "2", "9", "5", "6", "10", "4", "8", "7"

I have used this sequence of numbers to fill the other two larger lists also.

I have also used 3 different ways of performing the sort:

simpleList.Sort();
simpleList = simpleList.OrderBy(x => x[0]).ToList();
simpleList = simpleList.OrderBy(x => x[0]).AsParallel().ToList();

With the Sort method the actual list is sorted, but with the two other Linq ways of sorting the actual list is not updated when you do the sort, so that is why I need to use the ToList method.

This info graphic shows the results of the example measurements that I have done:

I have used the Stopwatch class to do the time measurements of the different sorts. The tests where done on a computer with Intel Pentium Dual Core with 2.7 GHz and 4GB of RAM. The OS was Windows 8 and the .Net version was 4.5.

It was very interesting to see that Linq and Ling.AsParallel methods are perform the same way in these examples.

The conclusion of this speed example is that you should always do your own measurements with real data to be able to select the correct way of sorting your list.