Sorting small arrays: Algorithm fight!

Please compose all posts in Emacs.

Moderators: phlip, Moderators General, Prelates

What is the world’s single undisputedly best algorithm for sorting small arrays?

Bubble sort
3
14%
Cycle sort
1
5%
Heap sort
1
5%
Insertion sort
12
57%
Selection sort
1
5%
Shell sort
1
5%
Sorting networks
2
10%
 
Total votes: 21

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3022
Joined: Sat May 09, 2009 11:55 pm UTC

Sorting small arrays: Algorithm fight!

Postby Qaanol » Tue Mar 24, 2015 3:38 pm UTC

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!
wee free kings

User avatar
Flumble
Yes Man
Posts: 1774
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Sorting small arrays: Algorithm fight!

Postby Flumble » Tue Mar 24, 2015 7:46 pm UTC

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.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3022
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Sorting small arrays: Algorithm fight!

Postby Qaanol » Tue Mar 24, 2015 9:52 pm UTC

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

User avatar
notzeb
Without Warning
Posts: 625
Joined: Thu Mar 08, 2007 5:44 am UTC
Location: a series of tubes

Re: Sorting small arrays: Algorithm fight!

Postby notzeb » Wed Mar 25, 2015 1:50 am UTC

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µ«V­jÕ«ZµjÖ­Zµ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«ZµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­Z

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 5243
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Sorting small arrays: Algorithm fight!

Postby Thesh » Wed Mar 25, 2015 2:36 am UTC

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.
Honesty replaced by greed, they gave us the reason to fight and bleed
They try to torch our faith and hope, spit at our presence and detest our goals

mousewiz
Posts: 107
Joined: Wed Oct 26, 2011 6:50 pm UTC

Re: Sorting small arrays: Algorithm fight!

Postby mousewiz » Wed Mar 25, 2015 8:24 pm UTC

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.

EvanED
Posts: 4313
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Sorting small arrays: Algorithm fight!

Postby EvanED » Wed Mar 25, 2015 8:28 pm UTC

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".

mousewiz
Posts: 107
Joined: Wed Oct 26, 2011 6:50 pm UTC

Re: Sorting small arrays: Algorithm fight!

Postby mousewiz » Wed Mar 25, 2015 9:44 pm UTC

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.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3022
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Sorting small arrays: Algorithm fight!

Postby Qaanol » Wed Mar 25, 2015 10:57 pm UTC

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

User avatar
Flumble
Yes Man
Posts: 1774
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Sorting small arrays: Algorithm fight!

Postby Flumble » Wed Mar 25, 2015 11:48 pm UTC

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.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3022
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Sorting small arrays: Algorithm fight!

Postby Qaanol » Thu Mar 26, 2015 12:10 am UTC

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.
wee free kings

User avatar
Flumble
Yes Man
Posts: 1774
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Sorting small arrays: Algorithm fight!

Postby Flumble » Thu Mar 26, 2015 2:13 pm UTC

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:

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Re: Sorting small arrays: Algorithm fight!

Postby Breakfast » Fri Mar 27, 2015 1:20 pm UTC

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."

User avatar
Xenomortis
Not actually a special flower.
Posts: 1373
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Sorting small arrays: Algorithm fight!

Postby Xenomortis » Fri Mar 27, 2015 1:39 pm UTC

So it's bogosort?
Image

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Re: Sorting small arrays: Algorithm fight!

Postby Breakfast » Fri Mar 27, 2015 3:00 pm UTC

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?

User avatar
Flumble
Yes Man
Posts: 1774
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Sorting small arrays: Algorithm fight!

Postby Flumble » Sat Mar 28, 2015 2:42 pm UTC

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

User avatar
SuperJedi224
Posts: 17
Joined: Thu Apr 16, 2015 4:19 pm UTC

Re: Sorting small arrays: Algorithm fight!

Postby SuperJedi224 » Fri Apr 17, 2015 5:35 pm UTC

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.
Striving for neutral good while caught in the crossfire of a struggle between lawful stupid, chaotic stupid, and, on occasion, just plain stupid.
Yeah, I'm wearing groucho glasses over a ninja mask. You have a problem with that?


Return to “Religious Wars”

Who is online

Users browsing this forum: No registered users and 3 guests