How to sort sequential GUIDs in C#?

Question

Sequential GUIDs are unique but are created with an order; that order is slightly unusual and is different to the order achieved when using the standard .NET Guid comparer.

I'm looking for a C# Guid comparer that will sort by the rules of sequential GUIDs.

== UPDATE==

I'm specifically referring to sequential GUIDs created by NewSequentialId() in SQL Server, although I realise now that the standard Win32 API call UuidCreateSequential() uses a different scheme to SQL Server (I assumed they were the same when I wrote the question).

== UPDATE 2==

petelids gives the answer below, using e.g. List<System.Data.SqlGuid>.Sort() gives the following sequence (using an initial list of GUIDs with a 1 in each 4 bit location)...

01000000-0000-0000-0000-000000000000
10000000-0000-0000-0000-000000000000
00010000-0000-0000-0000-000000000000
00100000-0000-0000-0000-000000000000
00000100-0000-0000-0000-000000000000
00001000-0000-0000-0000-000000000000
00000001-0000-0000-0000-000000000000
00000010-0000-0000-0000-000000000000
00000000-0100-0000-0000-000000000000
00000000-1000-0000-0000-000000000000
00000000-0001-0000-0000-000000000000
00000000-0010-0000-0000-000000000000
00000000-0000-0100-0000-000000000000
00000000-0000-1000-0000-000000000000
00000000-0000-0001-0000-000000000000
00000000-0000-0010-0000-000000000000
00000000-0000-0000-0001-000000000000
00000000-0000-0000-0010-000000000000
00000000-0000-0000-0100-000000000000
00000000-0000-0000-1000-000000000000
00000000-0000-0000-0000-000000000001
00000000-0000-0000-0000-000000000010
00000000-0000-0000-0000-000000000100
00000000-0000-0000-0000-000000001000
00000000-0000-0000-0000-000000010000
00000000-0000-0000-0000-000000100000
00000000-0000-0000-0000-000001000000
00000000-0000-0000-0000-000010000000
00000000-0000-0000-0000-000100000000
00000000-0000-0000-0000-001000000000
00000000-0000-0000-0000-010000000000
00000000-0000-0000-0000-100000000000

As opposed to the following order returned by List<System.Guid>.Sort()

00000000-0000-0000-0000-000000000001
00000000-0000-0000-0000-000000000010
00000000-0000-0000-0000-000000000100
00000000-0000-0000-0000-000000001000
00000000-0000-0000-0000-000000010000
00000000-0000-0000-0000-000000100000
00000000-0000-0000-0000-000001000000
00000000-0000-0000-0000-000010000000
00000000-0000-0000-0000-000100000000
00000000-0000-0000-0000-001000000000
00000000-0000-0000-0000-010000000000
00000000-0000-0000-0000-100000000000
00000000-0000-0000-0001-000000000000
00000000-0000-0000-0010-000000000000
00000000-0000-0000-0100-000000000000
00000000-0000-0000-1000-000000000000
00000000-0000-0001-0000-000000000000
00000000-0000-0010-0000-000000000000
00000000-0000-0100-0000-000000000000
00000000-0000-1000-0000-000000000000
00000000-0001-0000-0000-000000000000
00000000-0010-0000-0000-000000000000
00000000-0100-0000-0000-000000000000
00000000-1000-0000-0000-000000000000
00000001-0000-0000-0000-000000000000
00000010-0000-0000-0000-000000000000
00000100-0000-0000-0000-000000000000
00001000-0000-0000-0000-000000000000
00010000-0000-0000-0000-000000000000
00100000-0000-0000-0000-000000000000
01000000-0000-0000-0000-000000000000
10000000-0000-0000-0000-000000000000

Answer 1

There is a difference between the way Sql server and .NET sort guids.

There is a struct in the .NET framework called SqlGuid that should behave the same way as guids in Sql Server.

Consider the following example adapted from here:

List<Guid> a = new List<Guid>();
a.Add(new Guid("3AAAAAAA-BBBB-CCCC-DDDD-2EEEEEEEEEEE"));
a.Add(new Guid("2AAAAAAA-BBBB-CCCC-DDDD-1EEEEEEEEEEE"));
a.Add(new Guid("1AAAAAAA-BBBB-CCCC-DDDD-3EEEEEEEEEEE"));
Console.WriteLine("--Unsorted Guids--");
foreach (Guid g in a)
{
    Console.WriteLine("{0}", g);
}
a.Sort();
Console.WriteLine("--Sorted Guids--");
foreach (Guid g in a)
{
    Console.WriteLine("{0}", g);
}

List<SqlGuid> b = new List<SqlGuid>();
b.Add(new SqlGuid("3AAAAAAA-BBBB-CCCC-DDDD-2EEEEEEEEEEE"));
b.Add(new SqlGuid("2AAAAAAA-BBBB-CCCC-DDDD-1EEEEEEEEEEE"));
b.Add(new SqlGuid("1AAAAAAA-BBBB-CCCC-DDDD-3EEEEEEEEEEE"));
b.Sort();
Console.WriteLine("--Sorted SqlGuids--");
foreach (SqlGuid sg in b)
{
    Console.WriteLine("{0}", sg);
}

This produces the output:

--Unsorted Guids--
3aaaaaaa-bbbb-cccc-dddd-2eeeeeeeeeee
2aaaaaaa-bbbb-cccc-dddd-1eeeeeeeeeee
1aaaaaaa-bbbb-cccc-dddd-3eeeeeeeeeee
--Sorted Guids--
1aaaaaaa-bbbb-cccc-dddd-3eeeeeeeeeee
2aaaaaaa-bbbb-cccc-dddd-1eeeeeeeeeee
3aaaaaaa-bbbb-cccc-dddd-2eeeeeeeeeee
--Sorted SqlGuids--
2aaaaaaa-bbbb-cccc-dddd-1eeeeeeeeeee
3aaaaaaa-bbbb-cccc-dddd-2eeeeeeeeeee
1aaaaaaa-bbbb-cccc-dddd-3eeeeeeeeeee

The SqlGuid class has a constructor that takes a Guid and casting from one to the other also works so converting between them should be easy enough. Adding the following to the above code for example:

List<SqlGuid> c = a.Select(g => new SqlGuid(g)).ToList();
c.Sort();
Console.WriteLine("--Sorted SqlGuids 2--");
foreach (SqlGuid sg2 in c)
{
    Console.WriteLine("{0}", sg2);
}

Adds the output:

--Sorted SqlGuids 2--
2aaaaaaa-bbbb-cccc-dddd-1eeeeeeeeeee
3aaaaaaa-bbbb-cccc-dddd-2eeeeeeeeeee
1aaaaaaa-bbbb-cccc-dddd-3eeeeeeeeeee

Answer 2

Necromancing:
The answer covers the how, but not the why.
So, just for the record, SQL-server sorts them by bytes by order, that is to say a custom bytes order:

private static readonly int[] x_rgiGuidOrder = new int[16] // 16 Bytes = 128 Bit 
        {10, 11, 12, 13, 14, 15, 8, 9, 6, 7, 4, 5, 0, 1, 2, 3};

In other words, if you imagine a Guid as continuous UInt128-number, you need to partition it into 16 chunks of base 256, and arrange the chunks in their sort-order to produce SQL-compatible UIDs.

In case that is not clear:

public class SqlGuid
    : System.IComparable
    , System.IComparable<SqlGuid>
    , System.Collections.Generic.IComparer<SqlGuid>
    , System.IEquatable<SqlGuid>
{
    private const int NUM_BYTES_IN_GUID = 16;

    // Comparison orders.
    private static readonly int[] m_byteOrder = new int[16] // 16 Bytes = 128 Bit 
    {10, 11, 12, 13, 14, 15, 8, 9, 6, 7, 4, 5, 0, 1, 2, 3};

    private byte[] m_bytes; // the SqlGuid is null if m_value is null


    public SqlGuid(byte[] guidBytes)
    {
        if (guidBytes == null || guidBytes.Length != NUM_BYTES_IN_GUID)
            throw new System.ArgumentException("Invalid array size");

        m_bytes = new byte[NUM_BYTES_IN_GUID];
        guidBytes.CopyTo(m_bytes, 0);
    }


    public SqlGuid(System.Guid g)
    {
        m_bytes = g.ToByteArray();
    }


    public byte[] ToByteArray()
    {
        byte[] ret = new byte[NUM_BYTES_IN_GUID];
        m_bytes.CopyTo(ret, 0);
        return ret;
    }

    int CompareTo(object obj)
    {
        if (obj == null)
            return 1; // https://msdn.microsoft.com/en-us/library/system.icomparable.compareto(v=vs.110).aspx

        System.Type t = obj.GetType();

        if (object.ReferenceEquals(t, typeof(System.DBNull)))
            return 1;

        if (object.ReferenceEquals(t, typeof(SqlGuid)))
        {
            SqlGuid ui = (SqlGuid)obj;
            return this.Compare(this, ui);
        } // End if (object.ReferenceEquals(t, typeof(UInt128)))

        return 1;
    } // End Function CompareTo(object obj)


    int System.IComparable.CompareTo(object obj)
    {
        return this.CompareTo(obj);
    }


    int CompareTo(SqlGuid other)
    {
        return this.Compare(this, other);
    }


    int System.IComparable<SqlGuid>.CompareTo(SqlGuid other)
    {
        return this.Compare(this, other);
    }


    enum EComparison : int
    {
        LT = -1, // itemA precedes itemB in the sort order.
        EQ = 0, // itemA occurs in the same position as itemB in the sort order.
        GT = 1 // itemA follows itemB in the sort order.
    }


    public int Compare(SqlGuid x, SqlGuid y)
    {
        byte byte1, byte2;

        //Swap to the correct order to be compared
        for (int i = 0; i < NUM_BYTES_IN_GUID; i++)
        {
            byte1 = x.m_bytes[m_byteOrder[i]];
            byte2 = y.m_bytes[m_byteOrder[i]];
            if (byte1 != byte2)
                return (byte1 < byte2) ?  (int) EComparison.LT : (int) EComparison.GT;
        } // Next i 

        return (int) EComparison.EQ;
    }


    int System.Collections.Generic.IComparer<SqlGuid>.Compare(SqlGuid x, SqlGuid y)
    {
        return this.Compare(x, y);
    }


    public bool Equals(SqlGuid other)
    {
        return Compare(this, other) == 0;
    }


    bool System.IEquatable<SqlGuid>.Equals(SqlGuid other)
    {
        return this.Equals(other);
    }


}

Which means you can do it without SqlGuid, by doing:

public class TestClass 
{
    public static void Test()
    {
        System.Collections.Generic.List<System.Guid> ls = new System.Collections.Generic.List<System.Guid>();
        for(int i = 0; i < 100; ++i)
            ls.Add(System.Guid.NewGuid());

        ls.Sort(Compare);
    }


    public static int Compare(System.Guid x, System.Guid y)
    {
        const int NUM_BYTES_IN_GUID = 16;
        byte byte1, byte2;

        byte[] xBytes = new byte[NUM_BYTES_IN_GUID];
        byte[] yBytes = new byte[NUM_BYTES_IN_GUID];

        x.ToByteArray().CopyTo(xBytes, 0);
        y.ToByteArray().CopyTo(yBytes, 0);

        int[] byteOrder = new int[16] // 16 Bytes = 128 Bit 
            {10, 11, 12, 13, 14, 15, 8, 9, 6, 7, 4, 5, 0, 1, 2, 3};


        //Swap to the correct order to be compared
        for (int i = 0; i < NUM_BYTES_IN_GUID; i++)
        {
            byte1 = xBytes[byteOrder[i]];
            byte2 = yBytes[byteOrder[i]];
            if (byte1 != byte2)
                return (byte1 < byte2) ? -1 : 1;
        } // Next i 

        return 0;
    }

}

Although it will be more efficient with SqlGuid, because SqlGuid doesn't need to re-compute the byte-array every single time a comparison takes place.

Answer 3

Digressing: see Raymond Chen's How many ways are there to sort GUIDs?

Summarized as:

Algorithm	Byte array	String
memcmp	00 11 22 33 44 55 66 77 88 99 AA BB CC DD EE FF	{33221100-5544-7766-8899-AABBCCDDEEFF}
System.Guid / string	33 22 11 00 55 44 77 66 88 99 AA BB CC DD EE FF	{00112233-4455-6677-8899-AABBCCDDEEFF}
SqlGuid	CC DD EE FF AA BB 88 99 66 77 00 11 22 33 44 55	{FFEEDDCC-BBAA-9988-6677-001122334455}
Platform::Guid	33 22 11 00 77 66 55 44 BB AA 99 88 FF EE DD CC	{00112233-6677-4455-BBAA-9988FFEEDDCC}

And Java treats each GUID as a pair of signed 64-bit integers in big-endian format, see Another way to sort GUIDs: Java. In two columns (bits 0 and 64) the sort order is 89ABCDEF01234567. In the other columns, the sort order is 0123456789ABCDEF.