4

The common wisdom says that for small enough arrays insertion sort is the best. E.g., Timsort uses (binary) insertion sort for arrays up to 64 elements; from Wikipedia:

Some divide-and-conquer algorithms such as quicksort and mergesort sort by recursively dividing the list into smaller sublists which are then sorted. A useful optimization in practice for these algorithms is to use insertion sort for sorting small sublists, as insertion sort outperforms these more complex algorithms. The size of list for which insertion sort has the advantage varies by environment and implementation, but is typically between eight and twenty elements.

Is this actually correct? Are there any better alternatives?

In case this depends significantly on platform, I am most interested in .NET.

Alexey Romanov
  • 167,066
  • 35
  • 309
  • 487

4 Answers4

6

Yes, this is what I've learned in my algorithms classes, and this is also how sort is implemented in the C++ STL. From Wikipedia:

The June 2000 SGI C++ Standard Template Library stl_algo.h implementation of unstable sort uses the Musser introsort approach with the recursion depth to switch to heapsort passed as a parameter, median-of-3 pivot selection and the Sedgewick final insertion sort pass. The element threshold for switching to the simple insertion sort was 16.

I did some informal performance tests last year and C++ STL std::sort was about twice as fast as Array.Sort in .NET. I don't know how .NET Array.Sort is implemented, but in .NET, an access in an array requires a bounds check, unlike in C++, which could largely account for the performance difference.

Asik
  • 21,506
  • 6
  • 72
  • 131
  • Historically (around the time you wrote this) and in general, C# performance tests have been about twice as slow as native C. This would have changed over the last ten years or so with the many performance-related changes that have since entered the fold. – Engineer Feb 16 '23 at 08:18
  • Yeah I'm leaving the answer as-is for historical reference, but I hope people notice the date and take it with a grain of salt. – Asik Feb 17 '23 at 15:43
1

I've found it really depends on how much work the comparison function has to do. Like if I'm indirectly sorting rows of a worksheet, and each comparison involves fetching a row and then comparing possibly several columns, possibly mixing numeric and string compares, it can get slow.

On the other hand, if the length of the array is short, it depends on how many times per second you need to sort it, because even if it is relatively slow compared to what it could be, you may never notice the difference.

If I have any doubt, I just code up a merge sort and go with that. I've had bad experience with qsort not being stable and sometimes taking a long time. Hand-coded merge sort is simple, dependable, and fast enough.

Mike Dunlavey
  • 40,059
  • 14
  • 91
  • 135
0

There are no faster O(n log n) algorithms than insertion sort for small lists. However, there are some O(n^2) algorithms that do compete. Notably, selection sort is not one of these, although it is good under the rare situation where swaps and moves are expensive. Bubble sort and variants are also just plain bad.

Network sort: A sorting algorithm, always stable, no branches. It has terrible specs overall, but no branches means stellar performance on the tiniest of lists. The base case is: if(a<b) swap(a,b);

Insertion sort with batches: On each loop, sort 2-4 elements, then insert them together. This reduces the number of moves and compares by 25 to 37 percent for longer lists. The overall effect is optimization for lists in the size range 16 to 64.

warren
  • 563
  • 2
  • 13
-1

Since .NET is a language which doesn't compile to raw machinecode. I'd say calling an API function (which does use native code) probably is the fastest way to go

Toad
  • 15,593
  • 16
  • 82
  • 128
  • 1
    I wonder what the difference would be for sorting a 40 element array on c++ vs c# - and then I wonder if it would actually matter at all . – sirrocco Aug 14 '09 at 09:00
  • @sirrocco i am already thinking of it and researching howto's mixed mode etc' to avoid overhead of api calls or minimize.. – LoneXcoder Oct 04 '15 at 20:55