6

I've found out that inside the Array.Sort, 

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

gets called. Any ideas how this is implemented?

Roman Dzhabarov
  • 521
  • 4
  • 10
  • That method is implemented in native code, hence the `extern` keyword. Might be included in the reference source somewhere, but unless you're just curious to see how it's implemented, it's probably going to be faster than anything you can write in managed code. – Robert Rouhani Aug 14 '12 at 00:57
  • http://stackoverflow.com/questions/6842090/c-sharp-fastest-way-to-sort-an-array-in-descending-order – Alex Aug 14 '12 at 01:01
  • I'm curious because naive QuickSort is called unless default Comparer is used. So does that mean Array.Sort doesn't guarantee N*Log(N) worst case even if TrySZSort is called or not. – Roman Dzhabarov Aug 14 '12 at 01:01
  • @Xander: >>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 (Is that the same QuickSort?). From the answer, it is about nothing. Extremly fast, does that have measure? – Roman Dzhabarov Aug 14 '12 at 01:04

2 Answers2

12

You can get a fairly reliable copy of the CLR source code from the SSCLI20 source distribution. It was published in 2005 and, at the time, was a pretty accurate copy of CLR version 2. Never found an obvious discrepancy.

That's moved on since then, already 7 years ago and a rather major CLR version update since. But TrySZSort() is still around, those low-level implementations are highly self-preserving. You'll find it declared in clr/src/vm/ecall.cpp and mapped to ArrayHelper::TrySZSort(), a C++ method declared in clr/src/vm/arrayhelpers.cpp

It is otherwise very boring, it just calls a template class method named ArrayHelpers<T>.QuickSort(), specialized by array element type for value type elements.

Which is just the way Tony Hoare wrote it up 52 years ago. Albeit not in C++ ;)

You'll find the reason this code is written in C++ and not in C# in this answer.

Community
  • 1
  • 1
Hans Passant
  • 922,412
  • 146
  • 1,693
  • 2,536
4

Any ideas how this is implemented?

That method is implemented in native code, internal within the CLR itself. There are many methods like this on the very core, low level types. For example, quite a few of the methods on System.String are flagged InternalCall and implemented in the common language runtime itself.

Reed Copsey
  • 554,122
  • 78
  • 1,158
  • 1,373
  • Yes, I see that it is implemented in native code. But which kind of sort it hides: quick, heap, merge, tim, etc ? – Roman Dzhabarov Aug 14 '12 at 01:16
  • 3
    @RomanDzhabarov QuickSort - See: http://msdn.microsoft.com/en-us/library/kwx6zbd4.aspx "This method uses the QuickSort algorithm." – Reed Copsey Aug 14 '12 at 01:17
  • 1
    It typically is not just quick sort - below a certain level it switches to insertion sort. Also if it does too many recursions, it switches to heap sort I believe. Atlease visual studio C runtime library sort does these things. – Fakrudeen Aug 14 '12 at 08:34