Return to Answer

If you read about LINQ-to-objects (which is what we're using) it uses a Stable Quicksort to do it's sorting.

If you read about LINQ-to-objects (which is what we're using) it uses a Stable Quicksort to do it's sorting.

This solution is similar (has the same general effect) to the solution presented in this answer by Peter Taylor, but the key advantage here is that we can optimize it for our requirements. We've already made one optimization: skilling the first i elements. Just as well, that answer will not use constant space because of Select, which appears to use a significant amount of space.

This solution is similar (has the same general effect) to the solution presented in this answer by Peter Taylor, but the key advantage here is that we can optimize it for our requirements. We've already made one optimization: skilling the first i elements. Just as well, that answer will not use constant space because of Select, which appears to use a significant amount of space.

And believe it or not, for small, highly-variable data-sets this algorithm is the fastest (number count = 100, vary from 0 to short.MaxValue):

 Method | Mean | StdDev | Scaled | Scaled-StdDev | Gen 0 | Gen 1 | Gen 2 | Allocated |
------------------ |----------- |---------- |------- |-------------- |-------- |-------- |-------- |---------- |
 OriginalCode | 39.0327 us | 0.1790 us | 1.00 | 0.00 | 0.5615 | - | - | 9.91 kB |
 EBrownAnswer | 4.6140 us | 0.3984 us | 0.12 | 0.01 | - | - | - | 16 B |
 RubberDuckAnswer | 25.2577 us | 0.0717 us | 0.65 | 0.00 | 0.3499 | - | - | 8.39 kB |
 PeterTaylorAnswer | 34.0133 us | 0.1991 us | 0.87 | 0.01 | 0.0651 | - | - | 7.76 kB |
 HeslacherAnswer | 30.2370 us | 0.0269 us | 0.77 | 0.00 | 40.3239 | 40.3239 | 40.3239 | 131.42 kB |
 PaparazziAnswer | 17.5162 us | 0.0507 us | 0.45 | 0.00 | 0.5412 | - | - | 6.09 kB |