CODEWITHSUNDEEP
c#sorting
Projectile Fish
Projectile Fish

Reputation: 955

Fastest way to sort an array in descending order

Why is the following code

Array.Sort(values);
Array.Reverse(values);

much faster at sorting an array in descending order compared to

Array.Sort(values, (a,b)=>(-a.CompareTo(b)));

Code was run in Release mode outside of the debugger.

What is the most efficient way to produce a descending sort for arrays, preferably in a one liner?

Upvotes: 19

Views: 19104

Answers (4)

Petar Ivanov
Petar Ivanov

Reputation: 93030

That's a great question. I bet your values array is an array of primitive type!

It's really the sort that is dominant here, because the complexity of Reverse is O(n), while the sort is O(n logn).

The thing is that when sorting primitive types, .NET actually calls a native function, which is extremely fast - much faster that using a Comparison or Comparator.

The function is called TrySZSort:

[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
[SecurityCritical]
[MethodImpl(MethodImplOptions.InternalCall)]
private static bool TrySZSort(Array keys, Array items, int left, int right);

and here is how it's called in the Array class:

[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
[SecuritySafeCritical]
public static void Sort<T>(T[] array, int index, int length, IComparer<T> comparer)
{
  if (array == null)
    throw new ArgumentNullException("array");
  else if (index < 0 || length < 0)
    throw new ArgumentOutOfRangeException(length < 0 ? "length" : "index", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  else if (array.Length - index < length)
    throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
  else if (length > 1 && (comparer != null && comparer != Comparer<T>.Default || !Array.TrySZSort((Array) array, (Array) null, index, index + length - 1)))
    ArraySortHelper<T>.Default.Sort(array, index, length, comparer);
}

Upvotes: 23

leppie
leppie

Reputation: 117240

Delegates.

The call to the delegate is much slower than the default call to IComparable.CompareTo

Update:

If you want the same (or close) speed, implement the IComparer interface and pass that to the sort method.

http://msdn.microsoft.com/en-us/library/bzw8611x

Upvotes: 3

chrisaut
chrisaut

Reputation: 1086

Because in your second version it has to invoke your (anonymous) function each time it does a compare and then call .CompareTo inside that, so you have two indirections, whereas otherwise it can use build-in comparisons (for primitive types).

Basically you pay for function call overhead which I bet are eliminated for native primitive types when doing these sorts of operations. Though technically possible (I think), I doubt the Jitter is able to completely inline them in your second case.

Upvotes: 2

V4Vendetta
V4Vendetta

Reputation: 38210

As the link points out

Sort method here always ends up in an internal TrySZSort or QuickSort method when it doesn't throw an exception. The TrySZSort internal method is optimized for one-dimensional arrays, also known as "Zero" arrays or vectors

Because the TrySZSort method used in the base class libraries is implemented in native code, it has been heavily optimized. Therefore, this method is likely faster than any solution written in the C# language

Upvotes: 4

Related Questions