How does IOrderedEnumerable.ThenBy() in .Net work?

Question

I want to understand how ThenBy works in .Net. (I know how to use it, I just don't understand how Microsoft implemented it!)

According to the documentation, string_list.OrderBy(Function (x) x.length).ThenBy(Function (x) x) should output a list of strings ordered by length and then alphabetically. How could it possibly work?!? The first sort is by length. The second sort should undo the sorting of the first one!

Assume this code:

Dim sorted_by_length As IOrderedEnumerable(Of String)
sorted_by_length = string_list.OrderBy(Function (x) x.length)
sorted_by_length = sorted_by_length.ThenBy(Function

Here's me trying to implement the last line without using ThenBy:

Dim sorted_by_length As IOrderedEnumerable(Of String)
sorted_by_length = string_list.OrderBy(Function (x) x.length)
'my implementation of OrderBy:
Dim e as IEnumerator(Of String) = sorted_by_length.GetEnumerator
Do While e.MoveNext
    'I have no idea what to write here!
Loop

There's some magic going on here... Is there some e.GetPreviousKeySelector() function? In fact, I can't even write a function that returns IOrderedEnumerable!

Answer 1

How could it possibly work?!? The first sort is by length. The second sort should undo the sorting of the first one!

No, the second sort comparison is only consulted when the primary comparison finds two equal values.

The IOrderedEnumerable implementation does this by remembering all the comparisons, effectively - or, as another way of putting it, allowing you to build a comparison from "the current comparison and another one to consult when that returns 0".

I have a blog post series which goes into LINQ to Objects in some depth, providing a complete alternative implementation. The basis of IOrderedEnumerable is covered in part 26a and 26b, with more details and optimization in 26c and 26d.

In fact, I can't even write a function that returns IOrderedEnumerable!

You absolutely can - either by returning the value returned from OrderBy, or by implementing it yourself.