   [.net] .NET's Array.Sort implementation?
  Anyone who can find any ressources on there implementation other then the fact its a quicksort?I envy it its speed. I did a mergesort for use on linkedlist for my work place. It uses the new .NET 4.0 Task's so it can run on many cores. But it dosent come close to the speed of the quicksort.For the purpose of my mergesort its stable and that is what i need unlike the .NET sort. Also i wanned something with the same best and worst case running time. My own algoritm is fine. It consumes little memory and is pretty fast sorting some 60mil random ints in 2 min on dual cores and 30 seconds on a I7 8 core cpu.But on my pc that did my mergesort in 2 min on 60 million ints the quicksort implementation do the same in 7 seconds. Completly nullifying any fears i had about n^2 worst case.Im sure i could do some optimization of my own sort but i cant see how i can optimize it so much as to go from 2 min to 7 seconds. I could reuse a few(not really a few on big n) more objects in my algoritm this should speed thinks up but it still seems alot from 2 min to 7 sec. Maybe prealocate memory and map object in myself using unsafe code?Maybe its simply just becasue an array have better cache locality then a linkedlist?Anyone have any clue. I was thinking maybe trying to see if i could decompile the mscorlib.dll and see if i could figure anything from that but i havent read assembly since i finished school so thats properly a stretch.Anyway thanks for any reply :)edit:Maybe i didnt make it clear enough but i have tried to both google and "bing" this for 30 min now without finding anything on its implementation.   
  You can use Reflector to examine the implementation. It's pretty straightforward; the only real tricks are that it may take a code path that relies on an internalcall and it uses sort helpers to specialize for certain types of key. You could examine the SSCLI source to see what the internal call looks like if you were so inclined.   ;  I just did a test and realized im really stupid. I always get confused about pointers in managed code. or not so much confused as to i forget -.-Anyway. When i did my list i preallocated the array with ints for the .NET sort so ofc its super fast because of the locality in memory. I tried throwing in each int into one of my Node<T>'s used in my custom linkedlist Meaning it will be allocated on the heap at various places. This slowed things down considerably. Still the Sort is fast but it did 30 million in 50 seconds and my merge sort did it in 60 seconds.This really makes me wanna try and rewrite the allocation rutine so i preallocate all memory and and have it all together, forgot the word for it.That way i should be able to speed it up some.It should speed up merges because i keep good locality in memory?Am im on a completly wrong track here? or would that make sense?Thanks jpetrie ill give Reflector a look. I cant remember how much you can do in the free version  but i remember there ANT profiler being pretty awesome.   ;  I wouldnt worry about quicksort because of its worst case. Any good implimentation will make the worst case very very unlikely. (eg using something like median of 3/5, random pivot selection etc).The only concern is if someone actually tries to construct a worst case(which is actually a rather interesting exercise). Although I imagine this could be mitigated by using a secure random number algorithm etc, but that might cost a fair bit of performance.   ;  Yes ive also beginning to realize the quicksort really isnt bad. But tbh by now its simply just a excersie.There old code could only handle like 5000 lines in 40 min times because of there seriously crappy implementation. The new stuff i wrote for em do 10 times that in a few seconds. So you can talk about improvement :PBut its still annoying that the Array.Sort is so damn fast.   ;Quote:I just did a test and realized im really stupid. I always get confused about pointers in managed code. or not so much confused as to i forget -.-Anyway. When i did my list i preallocated the array with ints for the .NET sort so ofc its super fast because of the locality in memory. I tried throwing in each int into one of my Node<T>'s used in my custom linkedlist Meaning it will be allocated on the heap at various places. This slowed things down considerably. Still the Sort is fast but it did 30 million in 50 seconds and my merge sort did it in 60 seconds.This really makes me wanna try and rewrite the allocation rutine so i preallocate all memory and and have it all together, forgot the word for it.That way i should be able to speed it up some.It should speed up merges because i keep good locality in memory?Am im on a completly wrong track here? or would that make sense?Provide some code. You're using a lot of terms in what I suspect are incorrect ways, or ways that suggest you're misunderstanding underlying concepts. For example, one generally wants to avoid using pointers in managed code, because it requires unsafe code and the performance penalty can be severe -- there's really very little reason to use them.Similarly, allocation of objects in the CLR is generally quite fast -- the .NET allocator for heap objects is basically an arithmetic increment by the size of the object. Basically, your claims and metrics are unhelpful without providing source to back them up. We need to see your complete benchmark.   ;  Something like this i mean.No timing but the difference between the int and reference type should be considerable enough to notice.class Program    {   static void Main()   {  Random r = new Random();  int size = 30000000;  int[] intArray = new int[size];  for (int i = 0; i < size; ++i) intArray = r.Next();  Console.Out.WriteLine("Start int");  Array.Sort<int>(intArray);  Console.Out.WriteLine("Done int");  intArray = null;  GC.Collect();  ReferenceType[] refArray = new ReferenceType[size];  for (int i = 0; i < size; ++i) refArray = new ReferenceType(r.Next());  Console.Out.WriteLine("Start ref");  Array.Sort<ReferenceType>(refArray, (x, y) => { return x.value - y.value; });  Console.Out.WriteLine("Done ref");  Console.ReadLine();   }   public class ReferenceType   {  public int value;  public ReferenceType(int value)  { this.value = value;  }   }    };  I'm not sure what relevance this has to your prior assertions about pointers and allocations and whatnot -- and it should be expected that the second operation runs much slower given the significant difference between them. Otherwise, though, the benchmark is largely academic and doesn't have much bearing on real world use. What are you actually trying to accomplish?Note that your shenanigans with the call to GC.Collect() are in general ill-advised.   ;  Im merly trying to sort alot of generic objects based on a selected key using a delegate to select the key.And wondering how i could speed it up. By using better memory allocation.But my original question have been answered i think. Since the sort really isnt that much faster compared to my own using random numbers as the sorting key.And then wondering about the great difference in speed of the Array.Sort depending on if you give it int's a Class or a Struct.But i thank you for the replies :)   ;Quote: Im merly trying to sort alot of generic objects based on a selected key using a delegate to select the key.And wondering how i could speed it up. By using better memory allocation.But my original question have been answered i think. Since the sort really isnt that much faster compared to my own using random numbers as the sorting key.And then wondering about the great difference in speed of the Array.Sort depending on if you give it int's a Class or a Struct.The bottleneck in the Sort()implementation isn't going to be allocation -- it's just that some well-known types, like integers, end up getting special case optimizations. That can't be done in general, so the general case is slower.   