2

I have a list of reference types that are sorted by a DateTime property. Some of them have identical DateTime's. For example, multiple baseball games starting at the exact same time.

I want to confirm that OrderBy will sort the same way every time; that is to say because I provided the input in the order of A->B->C; that the output will also be A->B->C (all items have identical DateTime).

I wrote a unit test to confirm that the order is preserved. The test passed. But without really knowing what is going on I still don't feel confident.

Can someone please confirm the OrderBy behavior for me? I tried searching via google and couldn't find anything definitive.

sapbucket
  • 6,795
  • 15
  • 57
  • 94
  • What is the type of the collection your are calling OrderBy on? – Dave Nov 08 '17 at 21:33
  • Did you hit F12? Depending on your settings in VS this will load the source code from the .Net Framework and you can find out yourself. – Ric .Net Nov 08 '17 at 21:34
  • Have a look at this answer (it appears they will be the same with LINQ objects in a List) https://stackoverflow.com/questions/25922348/linq-orderby-does-it-always-return-the-same-ordered-list – d219 Nov 08 '17 at 21:37
  • @d219: yes that confirms what I am afraid of. That post indicates it is unstable. Someone just posted Orderby().Then() and that seems like a plausible solution in my case because I can force my own sort behavior and not rely on the default (unstable) behavior. Weird that he deleted the post I was about to accept it as the answer. – sapbucket Nov 08 '17 at 21:46
  • @sapbucket - from that link then, if you are using LINQ objects (rather than LINQ to SQL), I don't think you need to specify a second order if you know the items are always in the same order, if however you always wanted them to appear A, B, C but didn't know if the original order was A, B, C then yes you would have to. Note I've not played with this in practice though! – d219 Nov 08 '17 at 22:05

3 Answers3

4

The formal name for the concept you're asking about is called a Stable Sort.

Knowing this, you can check the documentation for Enumerable.OrderBy and see that it does, indeed, use a stable sorting algorithm. From near the end of the Remarks section:

This method performs a stable sort; that is, if the keys of two elements are equal, the order of the elements is preserved.

Additionally, there was some confustion with Linq-to-SQL in the comments on the question. If your data is already in a List<T> object you are not using Linq-to-SQL anymore. However, it's worth noting that Linq-to-SQL uses IQueryable.OrderBy rather than Enumerable.ORderBy, and IQueryable.OrderBy does not guarantee a stable sort. You may get a stable sort, but it depends on what the database engine does.

Joel Coehoorn
  • 399,467
  • 113
  • 570
  • 794
2

In short the OrderBy won't change the order if the OrderBy value is identical. So if the collection you called it on is ordered then it will keep that order. If it's a list then you're all good but other collection types do not guarantee order, such as dictionary or hashset so I imagine the order of them could change as you can't guarantee their order in the underlying collection.

Edit: as someone has mentioned in the comments linq to objects OrderBy is a stable (or deterministic sort) so the order will be the same every time and items considered equal will not have their order changed

Dave
  • 2,829
  • 3
  • 17
  • 44
  • It's exactly because of dictionary not guaranteeing order that I am concerned about the same for OrderBy on a list. By any chance do you know where I can read the official documentation on this behavior? – sapbucket Nov 08 '17 at 21:43
  • 1
    Let me have a hunt around. Lists remain in the same order because you can access them by index. So they have to stay in that order otherwise a call to myList[1] twice could yield different results for example which is not the case – Dave Nov 08 '17 at 21:44
  • 1
    Have a look here; https://msdn.microsoft.com/en-us/library/bb534966.aspx . Key paragraph is "This method performs a stable sort; that is, if the keys of two elements are equal, the order of the elements is preserved. In contrast, an unstable sort does not preserve the order of elements that have the same key." – d219 Nov 08 '17 at 21:47
1

First make sure you read the excelent answer of Joel.

That said, if you can not rely on Linq2Object's Stable Sort (EF for example), you also have the option of ThenBy:

OrderBy(c => c.MyDate).ThenBy(n => n.MyId)

This way you can apply a second order, if the first one has multiple same values.

Christian Gollhardt
  • 16,510
  • 17
  • 74
  • 111