Deterministic sort of a list of objects

Question

I need to sort a list of objects and an arbitrary sort property. If there are multiple objects in my list that have the same value for that sort property, then repeatedly sorting the same list will rearrange the members with the same value of sort property. To be clear, each time sort is run, a new list is generated and the order of members is arbitrary and not necessarily the same as it was the last time the list was sorted. Is there a way to avoid this?

Here is a code sample:

List<T> myList; // T is arbitrary and I doesn't implement any common interface
PropertyInfo sortPorperty = some property of T

var sortedList = myList.OrderBy(x => sortProperty.GetValue(x));

Multiple executions of this code will result in different order of the objects.

My initial idea is to also sort by the object itself

var sortedList = myList.OrderBy(x => sortProperty.GetValue(x)).ThenBy(x => x);

But as far as I can tell that will sort by hashcode and that is basically the memory location of an object so it would not be the same between runs. Is there anything else that would work?

Answer 1

If the type is serializable then you can use the serialization of the object to serve as the final sort criteria.

Use BinaryFormatter to generate a unique string for the object (which I have called Idem in this example) and use that as the final .ThenBy sorting criteria.

In this example I transformed the binary formatted version of the object to a base64 string (that's performance overhead for sure, and there are other approaches to get the the binary versions to compare nicely, but I'm just illustrating the general approach.)

I think this example has everything you asked for. Arbitrary type with no interface, uses a property as the OrderBy criteria, and does not rely on the initial order of the items to produce the same order of the output on subsequent runs.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization.Formatters.Binary;

public static class Extensions
{
    // Returns a string unique(TM) to this object.
    public static string Idem<T>(this T toSerialize)
    {
        BinaryFormatter formatter = new BinaryFormatter();
        var memoryStream = new MemoryStream();
        using (memoryStream)
        {
            formatter.Serialize(memoryStream, toSerialize);
            return Convert.ToBase64String(memoryStream.ToArray());
        }
    }
}

[Serializable()]
public class Person
{
    public Person(string name, string secret)
    {
        this.name = name;
        this.secret = secret;
    }

    private string secret; // some private info
    public string Nickname { get { return name; } } // some property
    public string name; // some public info

    public override string ToString() // a way to see the private info for this demo
    {
        return string.Format("{0} ({1})", name, secret);
    }
}

class Program
{
    static void Main(string[] args)
    {
        // You can rearrange the items in this list and they will always come out in the same order.
        List<Person> myList = new List<Person>() {
            new Person("Bob", "alpha"),
            new Person("Bob", "bravo"),
            new Person("Alice", "delta"),
            new Person("Bob", "echo"),
            new Person("Bob", "golf"),
            new Person("Bob", "foxtrot"),
        };
        PropertyInfo sortProperty = typeof(Person).GetProperty("Nickname");

        Random random = new Random();
        for (int i = 0; i < 3; ++i)
        {
            var randomList = myList.OrderBy(x => random.Next());


            var sortedList = randomList.OrderBy(x => sortProperty.GetValue(x))
                .ThenBy(x => x.Idem()); // Here's the magic "Then By Idem" clause.

            Console.WriteLine(string.Join(Environment.NewLine, sortedList));
            Console.WriteLine();
        }
    }
}