## Sorting small arrays: Algorithm fight!

**Moderators:** phlip, Moderators General, Prelates

### Sorting small arrays: Algorithm fight!

It’s a fight to the pain among algorithms for rapidly sorting small arrays (perhaps as the base case of a more general sorting function) and you must choose your champion for eternal victory!

Without further ado, here are the contenders (listed in alphabetic order):

Bubble sort — Hooray bubbles!

Cycle sort — Because writes are expensive!

Heap sort — This is totally a thing that exists.

Insertion sort — Because writes are cheap!

Selection sort — Because comparisons are cheap…right?

Shell sort — It’s shellsorts all the way down!

Sorting networks — Now completely branchless!

Choose wisely!

Without further ado, here are the contenders (listed in alphabetic order):

Bubble sort — Hooray bubbles!

Cycle sort — Because writes are expensive!

Heap sort — This is totally a thing that exists.

Insertion sort — Because writes are cheap!

Selection sort — Because comparisons are cheap…right?

Shell sort — It’s shellsorts all the way down!

Sorting networks — Now completely branchless!

Choose wisely!

wee free kings

### Re: Sorting small arrays: Algorithm fight!

Is there an unwritten rule that only in-place sorting algorithms may apply? And no quicksort or merge sort?

Currently I'm fond of sorting networks. The future is all about low-power processors everywhere , so we need to choose our datastructures and algorithms accordingly.

Currently I'm fond of sorting networks. The future is all about low-power processors everywhere , so we need to choose our datastructures and algorithms accordingly.

### Re: Sorting small arrays: Algorithm fight!

Flumble wrote:Is there an unwritten rule that only in-place sorting algorithms may apply? And no quicksort or merge sort?

Not a rule per se more like a suggestion. And those are two algorithms that tend to want a fast fallback routine for small arrays.

wee free kings

### Re: Sorting small arrays: Algorithm fight!

I didn't see Bogosort among the options... am disappoint. (Also, since Bogosort was designed with large arrays in mind, clearly the thing to do is to first pad your small array into a large array before passing it to Bogosort.)

Zµ«VjÕ«ZµjÖZµ«VµjÕZµkVZÕ«VµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZµkVZÕ«VµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZµkVZÕ«ZµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZ

### Re: Sorting small arrays: Algorithm fight!

Insertion sort, of course. You can use quicksort (or one of its hybrids) for large arrays, or merge sort when you need either a stable sort or parallelism.

Summum ius, summa iniuria.

### Re: Sorting small arrays: Algorithm fight!

I'm not sure this is a religious war so much as it is solvable by empiricism?

I vaguely recall insertion sort being the fast one on small arrays on modern PCs from my algorithm courses. So I picked that. But if I really needed to optimize a bunch of small array sorts, I'd probably just test and go with the fast one.

Or to make it religious anyways: clearly small arrays should only contain discrete values from a small range. Therefore you should learn that range and bucket sort them.

I vaguely recall insertion sort being the fast one on small arrays on modern PCs from my algorithm courses. So I picked that. But if I really needed to optimize a bunch of small array sorts, I'd probably just test and go with the fast one.

Or to make it religious anyways: clearly small arrays should only contain discrete values from a small range. Therefore you should learn that range and bucket sort them.

### Re: Sorting small arrays: Algorithm fight!

mousewiz wrote:I'm not sure this is a religious war so much as it is solvable by empiricism?

I vaguely recall insertion sort being the fast one on small arrays on modern PCs from my algorithm courses. So I picked that. But if I really needed to optimize a bunch of small array sorts, I'd probably just test and go with the fast one.

Or to make it religious anyways: clearly small arrays should only contain discrete values from a small range. Therefore you should learn that range and bucket sort them.

The problem with empiricism is that... "sorting what"? Distributions that are already sorted? Sorting integers (comparisons always cheap) or strings (comparisons are unboundedly expensive)? If strings, are they short? Long? Very different? Very similar?

Not to say that you shouldn't profile if you're the author of std::sort or whatever and try to pick use cases, but it's not as simple as "implement some, measure, pick fastest".

### Re: Sorting small arrays: Algorithm fight!

EvanED wrote:mousewiz wrote:I'm not sure this is a religious war so much as it is solvable by empiricism?

I vaguely recall insertion sort being the fast one on small arrays on modern PCs from my algorithm courses. So I picked that. But if I really needed to optimize a bunch of small array sorts, I'd probably just test and go with the fast one.

Or to make it religious anyways: clearly small arrays should only contain discrete values from a small range. Therefore you should learn that range and bucket sort them.

The problem with empiricism is that... "sorting what"? Distributions that are already sorted? Sorting integers (comparisons always cheap) or strings (comparisons are unboundedly expensive)? If strings, are they short? Long? Very different? Very similar?

Not to say that you shouldn't profile if you're the author of std::sort or whatever and try to pick use cases, but it's not as simple as "implement some, measure, pick fastest".

What I meant, but didn't state, was that I'd only apply empiricism once I knew what kind of data I was sorting. And what platform I was sorting it on. You're right that I didn't consider the author of std::sort, though the religious question there seems like it's less about the particular problem of sorting and more about the more general problem of which devs to appeal to.

So long as the library implementer notes the limitations of their "std::sort", I'm not too worried.

### Re: Sorting small arrays: Algorithm fight!

mousewiz wrote:I'm not sure this is a religious war so much as it is solvable by empiricism?

I vaguely recall insertion sort being the fast one on small arrays on modern PCs from my algorithm courses. So I picked that. But if I really needed to optimize a bunch of small array sorts, I'd probably just test and go with the fast one.

Well, this internet empirically says that for 6-element int arrays, an optimized branchless-swap sorting network is more than twice as fast as an optimized unrolled insertion sort, and a whopping nine times faster than a naively-implemented insertion sort (at least on one particular system). If that solitary datum reflects a trend, the fastest approach may well be a switch statement on the size of the array, which then employs the requisite sorting network.

wee free kings

### Re: Sorting small arrays: Algorithm fight!

Qaanol wrote:Not a rule per se more like a suggestion. And those are two algorithms that tend to want a fast fallback routine for small arrays.

Ah, I didn't know that those often fall back to selection sort and the likes. Still, parallel mergesort is definitely a competitor if you can spawn threads (or SIMD instructions with branching) in mere clock cycles.

Qaanol wrote:Well, this internet empirically says that for 6-element int arrays, an optimized branchless-swap sorting network is more than twice as fast as an optimized unrolled insertion sort, and a whopping nine times faster than a naively-implemented insertion sort (at least on one particular system). If that solitary datum reflects a trend, the fastest approach may well be a switch statement on the size of the array, which then employs the requisite sorting network.

The fastest approach is of course to allocate sizeof(element)^maxlength bytes and fill it with ordered lists, so you can sort the list with a simple lookup. Other O(n) algorithms, like quantum (bogo)sort, may also apply.

### Re: Sorting small arrays: Algorithm fight!

Flumble wrote:The fastest approach is of course to allocate sizeof(element)^maxlength bytes and fill it with ordered lists, so you can sort the list with a simple lookup.

I don’t think you have the right number of bytes there…or else I don’t follow your method. Let’s say we’re sorting pairs (ie. length-2 arrays) of 32-bit ints (so sizeof(int) is 4…provided that CHAR_BIT is 8.)

There are 2

^{32}possible values for the first int, and 2

^{32}possible values for the second. That’s 2

^{64}distinct pairs of ints. That lookup table just got somewhat unwieldy.

wee free kings

### Re: Sorting small arrays: Algorithm fight!

Qaanol wrote:Flumble wrote:The fastest approach is of course to allocate sizeof(element)^maxlength bytes and fill it with ordered lists, so you can sort the list with a simple lookup.

I don’t think you have the right number of bytes there…or else I don’t follow your method. Let’s say we’re sorting pairs (ie. length-2 arrays) of 32-bit ints (so sizeof(int) is 4…provided that CHAR_BIT is 8.)

Oops, I made a terrible mistake. It is indeed 2^(CHAR_BIT*sizeof(element)*maxlength)*sizeof(element) bytes. (a.k.a. possible_values^number_of_elements*size_of_array)

Sorting 6 8-bit values takes up some 280 TB. You may call it unwieldy, but who said there were any memory (or access time) restrictions?

### Re: Sorting small arrays: Algorithm fight!

Bogosort? Why not Robsort! It's the only way to go for small arrays. http://www.robsort.org/

"Robsort reads an array of integers and randomly arranges the order of those integers. It then checks to see if the array is sorted, if the array is sorted, robsort has done its job. If the array is not sorted, robsort ranomizes the array again. It continues this process untill it successfully sorts the array."

"Robsort reads an array of integers and randomly arranges the order of those integers. It then checks to see if the array is sorted, if the array is sorted, robsort has done its job. If the array is not sorted, robsort ranomizes the array again. It continues this process untill it successfully sorts the array."

- Xenomortis
- Not actually a special flower.
**Posts:**1429**Joined:**Thu Oct 11, 2012 8:47 am UTC

### Re: Sorting small arrays: Algorithm fight!

So it's bogosort?

### Re: Sorting small arrays: Algorithm fight!

Well sure... but it has the added bonuses of being less well known and always using multiple threads for maximum (in)efficiency. Who doesn't like misdirection and obscurity when trying to figure a bit of code out?

### Re: Sorting small arrays: Algorithm fight!

While quickly skimming over the text and seeing "number generation", I hoped it would be an algorithm that generates numbers, then checks if it's a permutation of the input and then checks if this permutation is sorted. I call dibs on /(fl.m)+sort/i. Probably flimflamsort. You can't flim flam "zim zam" –unless you perform about 2^56 trials.

Errr, that came out badly, especially considering a single trial can take years.

Anyway, I second the request for bogosort in the list.

Quantum sort should be on the list too.

1. Collect elements

2. ???

3. Return sorted list

Errr, that came out badly, especially considering a single trial can take years.

Anyway, I second the request for bogosort in the list.

Quantum sort should be on the list too.

1. Collect elements

2. ???

3. Return sorted list

- SuperJedi224
**Posts:**15**Joined:**Thu Apr 16, 2015 4:19 pm UTC

### Re: Sorting small arrays: Algorithm fight!

You know what I like? Gnome Sort. According to a java application I made for testing sorting algorithms, it doesn't take all that many optimizations to give it a 40-50% better average run time than selection sort for arrays of 6-20 elements.

### Who is online

Users browsing this forum: No registered users and 5 guests