Page 1 of 1

Sorting small arrays: Algorithm fight!

Posted: Tue Mar 24, 2015 3:38 pm UTC
by Qaanol
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!

Re: Sorting small arrays: Algorithm fight!

Posted: Tue Mar 24, 2015 7:46 pm UTC
by Flumble
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 8-) , so we need to choose our datastructures and algorithms accordingly.

Re: Sorting small arrays: Algorithm fight!

Posted: Tue Mar 24, 2015 9:52 pm UTC
by Qaanol
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.

Re: Sorting small arrays: Algorithm fight!

Posted: Wed Mar 25, 2015 1:50 am UTC
by notzeb
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.)

Re: Sorting small arrays: Algorithm fight!

Posted: Wed Mar 25, 2015 2:36 am UTC
by Thesh
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.

Re: Sorting small arrays: Algorithm fight!

Posted: Wed Mar 25, 2015 8:24 pm UTC
by mousewiz
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.

Re: Sorting small arrays: Algorithm fight!

Posted: Wed Mar 25, 2015 8:28 pm UTC
by EvanED
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!

Posted: Wed Mar 25, 2015 9:44 pm UTC
by mousewiz
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!

Posted: Wed Mar 25, 2015 10:57 pm UTC
by Qaanol
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.

Re: Sorting small arrays: Algorithm fight!

Posted: Wed Mar 25, 2015 11:48 pm UTC
by Flumble
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!

Posted: Thu Mar 26, 2015 12:10 am UTC
by Qaanol
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 232 possible values for the first int, and 232 possible values for the second. That’s 264 distinct pairs of ints. That lookup table just got somewhat unwieldy.

Re: Sorting small arrays: Algorithm fight!

Posted: Thu Mar 26, 2015 2:13 pm UTC
by Flumble
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? :roll:

Re: Sorting small arrays: Algorithm fight!

Posted: Fri Mar 27, 2015 1:20 pm UTC
by Breakfast
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."

Re: Sorting small arrays: Algorithm fight!

Posted: Fri Mar 27, 2015 1:39 pm UTC
by Xenomortis
So it's bogosort?

Re: Sorting small arrays: Algorithm fight!

Posted: Fri Mar 27, 2015 3:00 pm UTC
by Breakfast
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!

Posted: Sat Mar 28, 2015 2:42 pm UTC
by Flumble
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

Re: Sorting small arrays: Algorithm fight!

Posted: Fri Apr 17, 2015 5:35 pm UTC
by SuperJedi224
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.