# Sorting in C\#: OrderBy\.OrderBy or OrderBy\.ThenBy? What's more effective and why?

Suppose we need to sort the collection by multiple keys\. In C\#, we can do this with the help of OrderBy\(\)\.OrderBy\(\) or OrderBy\(\)\.ThenBy\(\)\. But what is the difference between these calls? To answer this question, we need to delve into the source code\.

![0991_OrderBy_ThenBy/image1.png](https://import.viva64.com/docx/blog/0991_OrderBy_ThenBy/image1.png)

The article has three chapters:

* **Background**\. For those who like to warm up a bit before reading an article\. Here you'll learn why I decided to do some research and find the difference between _OrderBy\(\)\.OrderBy\(\)_ and _OrderBy\(\)\.ThenBy\(\)_\.
* **Performance comparison**\. Here we'll compare the performance and memory consumption of these sorting methods\.
* **Behavior differences**\. Here we'll dive into the source code of \.NET to find out why these sorting methods differ in efficiency\.

## Background

It all started with the following article: "[Suspicious sortings in Unity, ASP\.NET Core, and more](https://pvs-studio.com/en/blog/posts/csharp/0928/)"\. The article describes cases where the order of _OrderBy\(\)\.OrderBy\(\)_ calls can lead to errors\. However, it turns out that sometimes developers intentionally use _OrderBy\(\)\.OrderBy\(\)_, not _OrderBy\(\)\.ThenBy\(\)_\.

Take a look at an example\. Let's say we have a _Wrapper_ class and an array of instances of the following type:

```cpp
class Wrapper
{
  public int Primary { get; init; }
  public int Secondary { get; init; }
}

var arr = new Wrapper[]
{
  new() { Primary = 1, Secondary = 2 },
  new() { Primary = 0, Secondary = 1 },
  new() { Primary = 2, Secondary = 1 },
  new() { Primary = 2, Secondary = 0 },
  new() { Primary = 0, Secondary = 2 },
  new() { Primary = 0, Secondary = 3 },
};
```

We want to sort this array: first by the _Primary_ value, then by _Secondary_\. 

If we perform sorting as follows — we make a mistake:

```cpp
var sorted = arr.OrderBy(p => p.Primary)
                .OrderBy(p => p.Secondary);
....
```

Here's the result:

```cpp
Primary: 2 Secondary: 0
Primary: 0 Secondary: 1
Primary: 2 Secondary: 1
Primary: 0 Secondary: 2
Primary: 1 Secondary: 2
Primary: 0 Secondary: 3
```

We get the wrong result\. To sort the collection correctly, we need to use _OrderBy\(\)\.ThenBy\(\)_:

```cpp
var sorted = arr.OrderBy(p => p.Primary)
                .ThenBy(p => p.Secondary);
....
```

Here's the result:

```cpp
Primary: 0 Secondary: 1
Primary: 0 Secondary: 2
Primary: 0 Secondary: 3
Primary: 1 Secondary: 2
Primary: 2 Secondary: 0
Primary: 2 Secondary: 1
```

However, we can also use _OrderBy\(\)\.OrderBy\(\)_ to get the correct result\. We just need to swap the calls\.

That's how we shouldn't do:

```cpp
var sorted = arr.OrderBy(p => p.Primary)
                .OrderBy(p => p.Secondary);
```

And that's how we should do:

```cpp
var sorted = arr.OrderBy(p => p.Secondary)
                .OrderBy(p => p.Primary);
```

It turns out that to get the correct result, we can use both options:

```cpp
// #1
var sorted1 = arr.OrderBy(p => p.Secondary)
                 .OrderBy(p => p.Primary);

// #2
var sorted2 = arr.OrderBy(p => p.Primary)
                 .ThenBy(p => p.Secondary);
```

I think the second option is more readable\.

When you see _OrderBy\(\)\.OrderBy\(\)_, you wonder: isn't there an [error](https://pvs-studio.com/en/blog/examples/v3078/)? So, it is better to use _OrderBy\(\)\.ThenBy\(\)_: the code is easier to read, and the developer's intention is clear\.

However, these sorting methods differ not only in appearance: their performance and memory consumption vary too\.

## Performance comparison

Let's experiment with the following code:

```cpp
struct Wrapper
{
  public int Primary { get; init; }
  public int Secondary { get; init; }
}

Wrapper[] arr = ....;

// #1
_ = arr.OrderBy(p => p.Secondary)
       .OrderBy(p => p.Primary)
       .ToArray();

// #2
_ = arr.OrderBy(p => p.Primary)
       .ThenBy(p => p.Secondary)
       .ToArray();
```

So, let's sum up the main points:

* _Wrapper_ is a structure with two integer properties\. We will use them as keys for sorting;
* _arr_ is an array of _Wrapper_ instances that we need to sort\. The way it was created is not important for tests\. We will measure the performance of sorting and obtaining the final array;
* there are two ways of sorting: the first one is _OrderBy\(\)\.OrderBy\(\)_, the second — _OrderBy\(\)\.ThenBy\(\)_;
* the _ToArray\(\)_ call is used to initiate sorting\.

To run tests, I took two sets of generated test data \(instances of the _Wrapper_ type\)\. In the first set, the spread of _Primary_ and _Secondary_ values is greater, in the second set it is less\. I wrote _Wrapper_ objects \(from 10 to 1,000,000\) in _arr_ and sorted them\.

The test project is running on \.NET 6\.

### Performance

I used [BenchmarkDotNet](https://benchmarkdotnet.org/) to track the performance\.

Below you can see how much it took to perform sorting and get an array\. We're not interested in absolute values — the difference between sorting methods is more important\.

Data set \#1:

|arr\\\.Length|10|100|1 000|10 000|100 000|1 000 000|
|---|---|---|---|---|---|---|
|OrderBy\\\(\\\)\\\.OrderBy\\\(\\\)|619 ns|9 us|170 us|2 ms|25\\\.8 ms|315 ms|
|OrderBy\\\(\\\)\\\.ThenBy\\\(\\\)|285 ns|4\\\.5 us|100 us|1\\\.4 ms|20\\\.4 ms|271 ms|
|\_Ratio\_|\_2\\\.17\_|\_2\_|\_1\\\.7\_|\_1\\\.43\_|\_1\\\.26\_|\_1\\\.16\_|

Data set \#2:

|arr\\\.Length|10|100|1 000|10 000|100 000|1 000 000|
|---|---|---|---|---|---|---|
|OrderBy\\\(\\\)\\\.OrderBy\\\(\\\)|553\\\.3 ns|8\\\.7 us|154 us|2\\\.1 ms|29\\\.5 ms|364 ms|
|OrderBy\\\(\\\)\\\.ThenBy\\\(\\\)|316\\\.4 ns|4\\\.2 us|80 us|1\\\.1 ms|16\\\.9 ms|240 ms|
|\_Ratio\_|\_1\\\.75\_|\_2\\\.07\_|\_1\\\.93\_|\_1\\\.91\_|\_1\\\.75\_|\_1\\\.52\_|

Let's move on and see the time difference if we perform several sortings at once\. To do this, we use the _for_ loop:

```cpp
for (int i = 0; i < iterNum; ++i)
{
  // Perform sorting
}
```

Here's the time \(in seconds\) spend to sort 1,000,000 instances of the _Wrapper_ type:

|Number of iterations|1|10|100|
|---|---|---|---|
|OrderBy\\\(\\\)\\\.OrderBy\\\(\\\)|0\\\.819|6\\\.52|65\\\.15|
|OrderBy\\\(\\\)\\\.ThenBy\\\(\\\)|0\\\.571|5\\\.21|42\\\.94|
|\_Ratio\_|\_1\\\.43\_|\_1\\\.25\_|\_1\\\.30\_|

Well, the difference in 20 seconds is worth considering\.

### Memory consumption

There is a similar thing with memory — _OrderBy\(\)\.OrderBy\(\)_ consumes more\. It is especially noticeable on large amounts of data and several iterations\.

Here's the difference in the number of objects created per iteration:

|Type|OrderBy\\\(\\\)\\\.OrderBy\\\(\\\)|OrderBy\\\(\\\)\\\.ThenBy\\\(\\\)|
|---|---|---|
|Int32\\\[\\\]|4|3|
|Comparison<Int32\\\>|2|1|
|Wrapper\\\[\\\]|3|2|

As the table suggests, _OrderBy\(\)\.OrderBy\(\)_ calls create two more arrays\. When I was running the test that had 100 sortings, I got a 1GB difference of allocated memory\.

It's important to note that the larger the sorted collection is, the larger the "extra" arrays are\. As a result, the amount of consumed memory also increases\.

## Behavior differences

And now it's time to look "under the hood"\. Just to remind you — we are considering two ways of sorting:

```cpp
// #1
_ = arr.OrderBy(p => p.Secondary)
       .OrderBy(p => p.Primary)
       .ToArray();

// #2
_ = arr.OrderBy(p => p.Primary)
       .ThenBy(p => p.Secondary)
       .ToArray();
```

To understand the difference, we need to analyze:

* methods that are called;
* state of objects for whom methods are called;
* the execution flow\.

The source code of \.NET 6 is available on [GitHub](https://github.com/dotnet/runtime)\.

### Top\-level methods

We need to discuss three top\-level methods: _OrderBy_, _ThenBy_, and _ToArray_\. Let's consider each of them\.

**OrderBy**

_OrderBy_ is an extension method that returns an instance of the _OrderedEnumerable<TElement, TKey\>_ type:

```cpp
public static IOrderedEnumerable<TSource> 
OrderBy<TSource, TKey>(this IEnumerable<TSource> source, 
                       Func<TSource, TKey> keySelector)
  => new OrderedEnumerable<TSource, 
                           TKey>(source, keySelector, null, false, null);
```

Here's the_ OrderedEnumerable<TElement, TKey\>_ constructor:

```cpp
internal OrderedEnumerable( IEnumerable<TElement> source, 
                            Func<TElement, TKey> keySelector, 
                            IComparer<TKey>? comparer, 
                            bool descending, 
                            OrderedEnumerable<TElement>? parent
                           ) : base(source)
{
  ....
  _parent = parent;
  _keySelector = keySelector;
  _comparer = comparer ?? Comparer<TKey>.Default;
  _descending = descending;
}
```

Here we're interested in the base constructor call — _base\(source\)_\. The base type is _OrderedEnumerable<TElement\>_\. The constructor looks as follows:

```cpp
protected OrderedEnumerable(IEnumerable<TElement> source) 
  => _source = source;
```

Let's brush up on what we've already discussed: as a result of the _OrderBy_ call, the _OrderedEnumerable<TElement, TKey\>_ instance is created\. Its state is determined by the following fields:

* \_source;
* \_parent;
* \_keySelector;
* \_comparer;
* \_descending\.

**ThenBy**

_ThenBy_ is an extension method:

```cpp
public static IOrderedEnumerable<TSource> 
ThenBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, 
                      Func<TSource, TKey> keySelector)
{
  ....
  return source.CreateOrderedEnumerable(keySelector, null, false);
}
```

In our case, the type of the _source_ variable is _OrderedEnumerable<TElement, TKey\>_\. Let's take a look at the implementation of the _CreateOrderedEnumerable_ method that will be called:

```cpp
IOrderedEnumerable<TElement> 
IOrderedEnumerable<TElement>
 .CreateOrderedEnumerable<TKey>(Func<TElement, TKey> keySelector, 
                                IComparer<TKey>? comparer, 
                                bool descending) 
  => new OrderedEnumerable<TElement, 
                           TKey>(_source, 
                                 keySelector, 
                                 comparer, 
                                 @descending, 
                                 this);
```

We see that the constructor of the _OrderedEnumerable<TElement, TKey\>_ type \(that we've already discussed in the _OrderBy_ section\) is called\. The arguments of the call differ, and, as a result, the state of the created object differs\.

Let's brush it up: _ThenBy_ \(like _OrderBy_\), in our case returns an instance of the _OrderedEnumerable<TElement, TKey\>_ type\.

**ToArray**

_ToArray_ is an extension method:

```cpp
public static TSource[] ToArray<TSource>(this IEnumerable<TSource> source)
{
  ....
  return source is IIListProvider<TSource> arrayProvider
    ? arrayProvider.ToArray()
    : EnumerableHelpers.ToArray(source);
}
```

In both cases, _source_ are the instances of the _OrderedEnumerable<TElement, TKey\>_ type\. This type implements the _IIlistProvider<TSource\>_ interface\. Therefore, the execution will go via the _arrayProvider\.ToArray\(\)_ call\. In fact, the _OrderedEnumerable<TElement\>\.ToArray_ method will be called:

```cpp
public TElement[] ToArray()
{
  Buffer<TElement> buffer = new Buffer<TElement>(_source);

  int count = buffer._count;
  if (count == 0)
  {
    return buffer._items;
  }

  TElement[] array = new TElement[count];
  int[] map = SortedMap(buffer);
  for (int i = 0; i != array.Length; i++)
  {
    array[i] = buffer._items[map[i]];
  }

  return array;
}
```

And here the main differences occur\. Before we continue to dive deeper, we need to examine the state of the objects we will be working with\.

### States of OrderedEnumerable objects

Let's get back to the source examples:

```cpp
// #1
_ = arr.OrderBy(p => p.Secondary) // Wrapper[] -> #1.1
       .OrderBy(p => p.Primary)   // #1.1 -> #1.2
       .ToArray();                // #1.2 -> Wrapper[]

// #2
_ = arr.OrderBy(p => p.Primary)  // Wrapper[] -> #2.1
       .ThenBy(p => p.Secondary) // #2.1 -> #2.2
       .ToArray();               // #2.2 -> Wrapper[]
```

We need to compare four objects arranged in pairs:

* \#1\.1 and \#2\.1 are objects created by the first _OrderBy_ calls in both examples;
* \#1\.2 and \#2\.2 are objects created by the second _OrderBy_ call in the first example and by the _ThenBy_ call in the second example\.

As a result, we get 2 tables for comparing the states of objects\.

Here are the states of objects created by the first _OrderBy_ calls:

|Field|Object \\\#1\\\.1|Object \\\#2\\\.1|
|---|---|---|
|\\\_source|arr|arr|
|\\\_comparer|Comparer<Int32\\\>\\\.Default|Comparer<Int32\\\>\\\.Default|
|\\\_descending|false|false|
|\\\_keySelector|p \\\=\\\> p\\\.Secondary|p \\\=\\\> p\\\.Primary|
|\\\_parent|null|null|

This pair is identical\. Only selectors differ\.

Here are the states of objects created by the second call of _OrderBy_ \(\#1\.2\) and _ThenBy_ \(\#2\.2\):

|Field|Object \\\#1\\\.2|Object \\\#2\\\.2|
|---|---|---|
|\\\_source|\*\*Object \\\#1\\\.1\*\*|\*\*arr\*\*|
|\\\_comparer|Comparer<Int32\\\>\\\.Default|Comparer<Int32\\\>\\\.Default|
|\\\_descending|false|false|
|\\\_keySelector|p \\\=\\\> p\\\.Primary|p \\\=\\\> p\\\.Secondary|
|\\\_parent|\*\*null\*\*|\*\*Object \\\#2\\\.1\*\*|

Here the selectors also differ — and this is expected\. Curious that _\_source_ and _\_parent_ fields differ\. The state of the object in case of the _ThenBy_ \(\#2\.2\) call seems more correct: the reference to the source collection is saved, and there's a "parent" — the result of the previous sorting\.

### Execution flow

Now we need to find out how the state of objects affects the execution flow\. 

Let's get back to the _ToArray_ method:

```cpp
public TElement[] ToArray()
{
  Buffer<TElement> buffer = new Buffer<TElement>(_source);

  int count = buffer._count;
  if (count == 0)
  {
    return buffer._items;
  }

  TElement[] array = new TElement[count];
  int[] map = SortedMap(buffer);
  for (int i = 0; i != array.Length; i++)
  {
    array[i] = buffer._items[map[i]];
  }

  return array;
}
```

Keep in mind that objects received by different calls have different _\_source_ fields:

* _OrderBy\(\)\.OrderBy\(\)_ refers to the_ OrderedEnumerable<TElement, TKey\>_ instance;
* _OrderBy\(\)\.ThenBy\(\)_ refers to the _Wrapper\[\]_ instance\.

Let's consider the determining of the _Buffer<TElement\>_ type:

```cpp
internal readonly struct Buffer<TElement>
{
  internal readonly TElement[] _items;
  internal readonly int _count;

  internal Buffer(IEnumerable<TElement> source)
  {
    if (source is IIListProvider<TElement> iterator)
    {
      TElement[] array = iterator.ToArray();
      _items = array;
      _count = array.Length;
    }
    else
    {
      _items = EnumerableHelpers.ToArray(source, out _count);
    }
  }
}
```

This is where behavior starts to differ:

* for _OrderBy\(\)\.OrderBy\(\)_ calls the execution follows the then branch, since _OrderedEnumerable_ implements the _IIListProvider<TElement\>_ interface;
* for _OrderBy\(\)\.ThenBy\(\)_ calls the execution follows the else branch, because arrays \(in our case_ _it is_ Wrapper\[\]_\) do not implement this interface\.

In the first case, we are getting back to the _ToArray_ method that was given above\. Then, we get into the _Buffer_ constructor again, but the execution will follow the else branch, because the _\_source_ of the object \#1\.1 is _Wrapper\[\]_\.

_EnumerableHelpers\.ToArray_ just creates a copy of the array:

```cpp
internal static T[] ToArray<T>(IEnumerable<T> source, out int length)
{
  if (source is ICollection<T> ic)
  {
    int count = ic.Count;
    if (count != 0)
    {        
      T[] arr = new T[count];
      ic.CopyTo(arr, 0);
      length = count;
      return arr;
    }
  }
  else
    ....

  ....
}
```

The execution follows the then branch\. I omitted the rest of code, because in our case it is unimportant\.

The difference is clearer in call stacks\. Pay attention to the bold "extra" calls:

|Call stack for OrderBy\\\(\\\)\\\.OrderBy\\\(\\\)|Call stack for OrderBy\\\(\\\)\\\.ThenBy\\\(\\\)|
|---|---|
|||
|EnumerableHelpers\\\.ToArray|EnumerableHelpers\\\.ToArray|
|\*\*Buffer\\\.ctor\*\*|Buffer\\\.ctor|
|\*\*OrderedEnumerable\\\.ToArray\*\*|OrderedEnumerable\\\.ToArray|
|Buffer\\\.ctor|Enumerable\\\.ToArray|
|OrderedEnumerable\\\.ToArray|Main|
|Enumerable\\\.ToArray||
|Main||

By the way, this also explains the difference in the number of created objects\. Here's the table we discussed previously:

|Type|OrderBy\\\(\\\)\\\.OrderBy\\\(\\\)|OrderBy\\\(\\\)\\\.ThenBy\\\(\\\)|
|---|---|---|
|Int32\\\[\\\]|4|3|
|Comparison<Int32\\\>|2|1|
|Wrapper\\\[\\\]|3|2|

The most interesting arrays here are: _Int32\[\]_ and _Wrapper\[\]_\. They arise because the execution flow unnecessarily passes via the _OrderedEnumerable<TElement\>\.ToArray_ method once again:

```cpp
public TElement[] ToArray()
{
  ....
  TElement[] array = new TElement[count];
  int[] map = SortedMap(buffer);
  ....
}
```

Just to remind you — the sizes of _array_ and _map_ arrays depend on the size of the sorted collection: the larger it is, the larger the overhead will be — because of the unnecessary _OrderedEnumerable<TElement\>\.ToArray_ call\.

The same thing is with the performance\. Let's take another look at the code of the _OrderedEnumerable<TElement\>\.ToArray_ method:

```cpp
public TElement[] ToArray()
{
  Buffer<TElement> buffer = new Buffer<TElement>(_source);

  int count = buffer._count;
  if (count == 0)
  {
    return buffer._items;
  }

  TElement[] array = new TElement[count];
  int[] map = SortedMap(buffer);
  for (int i = 0; i != array.Length; i++)
  {
    array[i] = buffer._items[map[i]];
  }

  return array;
}
```

We are interested in the _map_ array\. It describes the relationship between the positions of elements in arrays:

* index is the position of an element in the resulting array;
* the index value is the position in the source array\.

Let's say _map\[5\] \=\= 62_\. This means that the element takes the 62nd position in the source array, and the 5th position in the resulting array\.

To get a so\-called "relationship map", the _SortedMap_ method is used:

```cpp
private int[] SortedMap(Buffer<TElement> buffer) 
  => GetEnumerableSorter().Sort(buffer._items, buffer._count);
```

Here's the _GetEnumerableSorter_ method:

```cpp
private EnumerableSorter<TElement> GetEnumerableSorter() 
  => GetEnumerableSorter(null);
```

Let's take a look at the method overload:

```cpp
internal override EnumerableSorter<TElement> 
GetEnumerableSorter(EnumerableSorter<TElement>? next)
{
  ....

  EnumerableSorter<TElement> sorter = 
    new EnumerableSorter<TElement, TKey>(_keySelector, 
                                         comparer, 
                                         _descending, 
                                         next);
  if (_parent != null)
  {
    sorter = _parent.GetEnumerableSorter(sorter);
  }

  return sorter;
}
```

Here comes up another difference between the sorting methods that we are discussing:

* _OrderBy\(\)\.OrderBy\(\)_: _\_parent_ of the object \#1\.2 is _null_\. As a result, one instance of _EnumerableSorter_ is created\.
* _OrderBy\(\)\.ThenBy\(\)_: _\_parent_ of the object \#2\.2 points to the object \#2\.1\. This means that two _EnumerableSorter_ instances related to each other will be created\. This happens because the _\_parent\.GetEnumerableSorter\(sorter\)_ method is called once again\.

Here's the called _EnumerableSorter_ constructor:

```cpp
internal EnumerableSorter(
  Func<TElement, TKey> keySelector, 
  IComparer<TKey> comparer, 
  bool descending, 
  EnumerableSorter<TElement>? next)
{
  _keySelector = keySelector;
  _comparer = comparer;
  _descending = descending;
  _next = next;
}
```

The constructor just initializes the object fields\. There is another field that is not used in the constructor — _\_keys_\. It will be initialized later in the _ComputeKeys_ method\.

Let's consider what the fields are responsible for\. To do this, let's discuss one of the sorting ways:

```cpp
_ = arr.OrderBy(p => p.Primary)
       .ThenBy(p => p.Secondary)
       .ToArray();
```

To perform sorting via _OrderBy_, an instance of _EnumerableSorter_ will be created\. It has the following fields:

* _\_keySelector_: a delegate responsible for mapping the source object to the key\. In our case it's _Wrapper_ \-\> _int_\. The delegate: _p \=\> p\.Primary_;
* _\_comparer_: a comparator used to compare keys\. _Comparer<T\>\.Default_ if not explicitly specified;
* _\_descenging_: a flag meaning that the collection is sorted in descending order;
* _\_next_: a reference to the _EnumerableSorter_ object responsible for the following sorting criteria\. In the example above, there is a reference to an object that was created for sorting by the criterion from _ThenBy_\.

After the _EnumerableSorter_ instance was created and initialized, the _Sort_ method is called for it:

```cpp
private int[] SortedMap(Buffer<TElement> buffer) 
  => GetEnumerableSorter().Sort(buffer._items, buffer._count);
```

Here's the body of the _Sort_ method:

```cpp
internal int[] Sort(TElement[] elements, int count)
{
  int[] map = ComputeMap(elements, count);
  QuickSort(map, 0, count - 1);
  return map;
}
```

Here's the _ComputeMap_ method:

```cpp
private int[] ComputeMap(TElement[] elements, int count)
{
  ComputeKeys(elements, count);
  int[] map = new int[count];
  for (int i = 0; i < map.Length; i++)
  {
    map[i] = i;
  }

  return map;
}
```

Let's take a look at the _ComputeKeys_ method:

```cpp
internal override void ComputeKeys(TElement[] elements, int count)
{
  _keys = new TKey[count];
  for (int i = 0; i < count; i++)
  {
    _keys[i] = _keySelector(elements[i]);
  }

  _next?.ComputeKeys(elements, count);
}
```

In this method, the _\_keys_ array of the _EnumerableSorter_ instance is initialized\. The _\_next?\.ComputeKeys\(elements, count\)_ call allows initializing the entire chain of related _EnumerableSorter_ objects\.

Why do we need the _\_keys_ field? The array stores the results of calling the selector on each element of the source array\. So, we get an array of keys that will be used to perform sorting\.

Here's an example:

```cpp
var arr = new Wrapper[]
{
  new() { Primary = 3, Secondary = 2 },
  new() { Primary = 3, Secondary = 1 },
  new() { Primary = 1, Secondary = 0 }
};

_ = arr.OrderBy(p => p.Primary)
       .ThenBy(p => p.Secondary)
       .ToArray();
```

In this example, two related _EnumerableSorter_ instances will be created\.

|Field|EnumerableSorter \\\#1|EnumerableSorter \\\#2|
|---|---|---|
|\\\_keySelector|p \\\=\\\> p\\\.Primary|p \\\=\\\> p\\\.Secondary|
|\\\_keys|\\\[3, 3, 1\\\]|\\\[2, 1, 0\\\]|

Thus, _\_keys_ stores sorting keys for each element of the source array\.

Let's get back to the _ComputeMap_ method:

```cpp
private int[] ComputeMap(TElement[] elements, int count)
{
  ComputeKeys(elements, count);
  int[] map = new int[count];
  for (int i = 0; i < map.Length; i++)
  {
    map[i] = i;
  }

  return map;
}
```

After calling the _ComputeKeys_ method, the _map_ array is created and initialized\. This is the array that describes the relationship between the positions in the source and resulting arrays\. In this method, it still describes the i \-\> i relationship\. This means that the positions in the source array coincide with the positions in the resulting array\.

Let's get back to the _Sort_ method:

```cpp
internal int[] Sort(TElement[] elements, int count)
{
  int[] map = ComputeMap(elements, count);
  QuickSort(map, 0, count - 1);
  return map;
}
```

We are interested in the _QuickSort_ method that makes the _map_ array to look the way we need\. Right after this operation we get the correct relationship between the positions of elements in the source array and in the resulting one\.

Here's the body of the _QuickSort_ method:

```cpp
protected override void QuickSort(int[] keys, int lo, int hi) 
  => new Span<int>(keys, lo, hi - lo + 1).Sort(CompareAnyKeys);
```

We won't dive into the details of _Span_ and its _Sort_ method\. Let's focus on the fact that it sorts the array considering the _Comparison_ delegate:

```cpp
public delegate int Comparison<in T>(T x, T y);
```

It's a classic delegate for comparison\. It takes two elements, compares them, and returns the value:

* < 0 if _x_ is less than _y_;
* 0 if _x_ is equal to _y_;
* \> 0 if _x_ is greater than _y_\.

In our case, the _CompareAnyKeys_ method is used for comparison:

```cpp
internal override int CompareAnyKeys(int index1, int index2)
{
  Debug.Assert(_keys != null);

  int c = _comparer.Compare(_keys[index1], _keys[index2]);
  if (c == 0)
  {
    if (_next == null)
    {
      return index1 - index2; // ensure stability of sort
    }

    return _next.CompareAnyKeys(index1, index2);
  }

  // ....
  return (_descending != (c > 0)) ? 1 : -1;
}
```

So, let's see what we have:

```cpp
int c = _comparer.Compare(_keys[index1], _keys[index2]);
if (c == 0)
  ....

return (_descending != (c > 0)) ? 1 : -1;
```

Two elements are compared via a comparator written in _\_comparer_\. Since we have not explicitly set any comparator, _Comparer<T\>\.Default_ is used \(in our case – _Comparer<Int32\>\.Default_\)\. 

If elements are not equal, the _c \=\= 0_ condition is not executed, and the execution flow goes to _return_\. The _\_descending_ field stores the information on how the elements are sorted — in descending or ascending order\. If necessary, the field is used to correct the value returned by the method\.

But what if the elements are equal?

```cpp
if (c == 0)
{
  if (_next == null)
  {
    return index1 - index2; // ensure stability of sort
  }

  return _next.CompareAnyKeys(index1, index2);
}
```

Here come the chains of _EnumerableSorter_ instances related to each other\. If the compared keys are equal, a check is performed to see if there are any other sorting criteria\. If there is \(_\_next \!\= null_\), the comparison is performed via them\.

It turns out that all sorting criteria are considered in one call of the _Sort_ method\.

What happens if we use _OrderBy\(\)\.OrderBy\(\)_? To find out, let's get back to creating the _EnumerableSorter_ instance:

```cpp
internal override EnumerableSorter<TElement> 
GetEnumerableSorter(EnumerableSorter<TElement>? next)
{
  ....

  EnumerableSorter<TElement> sorter = 
    new EnumerableSorter<TElement, TKey>(_keySelector, 
                                         comparer, 
                                         _descending, 
                                         next);
  if (_parent != null)
  {
    sorter = _parent.GetEnumerableSorter(sorter);
  }

  return sorter;
}
```

The _\_parent_ value of the object obtained as a result of the second _OrderBy_ call is _null_\. This means that one _EnumerableSorter_ instance is created\. It is not related to something, the value of _\_next_ is _null_\. 

It turns out that we need to perform all the actions described above twice\. We've already discussed how this affects the performance\. To remind you, I'd duplicate one of the tables given above\.

Here's the time \(in seconds\) spend to sort 1,000,000 instances of the _Wrapper_ type:

|Number of iterations|1|10|100|
|---|---|---|---|
|OrderBy\\\(\\\)\\\.OrderBy\\\(\\\)|0\\\.819|6\\\.52|65\\\.15|
|OrderBy\\\(\\\)\\\.ThenBy\\\(\\\)|0\\\.571|5\\\.21|42\\\.94|

## The difference in a nutshell

The _OrderBy_ and _ThenBy_ methods create _OrderedEnumerable_ instances that are used to perform sorting\. Instances of the _EnumerableSorter_ type help perform sorting\. They affect the algorithm, use specified selectors and a comparator\.

The main difference between _OrderBy\(\)\.OrderBy\(\)_ and _OrderBy\(\)\.ThenBy\(\)_ calls is the relations between objects\.

**OrderBy\(\)\.OrderBy\(\)**\. There are no relations between _OrderedEnumerable_ or _EnumerableSorter_\. As a result, "extra" objects are created — instead of one sorting, we get two\. Memory consumption is growing, and the code runs slower\.

**OrderBy\(\)\.ThenBy\(\)**\. Both _OrderedEnumerable_ and _EnumerableSorter_ instances are related\. Because of this, one sorting operation is performed by several criteria at once\. Extra objects are not created\. Memory consumption is reduced, and the code runs faster\.

## Conclusion

The code that uses _OrderBy\(\)\.ThenBy\(\)_ instead of _OrderBy\(\)\.OrderBy\(\)_:

* is better to read;
* is less error prone;
* works faster;
* consumes less memory\.



Follow me on [Twitter](https://twitter.com/_SergVasiliev_), if you are interested in such publications\.