Masmlib Quick Sort

[cork]

The gauntlets been thrown. It would be cool to see a bad-ass brawl in the mud for bragging rights.

[hutch--]

 :bg

Sad to say its all been done before, thats what we have the Laboratory for. Post code in there to get it beaten to death.

[jj2007]

Guys we should have a contest!

How does this sound...

Someone could produce a 50 MB file of strings between 5 and 40 characters long (length is random).

Great idea. It should also handle Unicode and have an "ignore case" option, though. Don't forget conditional breaks, leading whitespace and the like :U

[Rockoon]

The problem is still not fully specified. How much extra memory (including both stack and heap) would be afforded?

Clearly a radix sort will dominate more and more as extra memory increases.

If extra memory is set to something small, like on the scale of O(log n), then things like MergeSort become much more complicated (an in-place merge sort variant does exist, tho) .. the common implementation of MergeSort is at the O(n) scale in space requirements.

O(log n) space is required if we wish to support any binary decimation recursive functions (MergeSort and QuickSort)
O(n) space would be the bare minimum for Radix and other bucket sorts (and not easy to use in practice)

If all we are doing is sorting strings with no extra values assigned to the elements, then there is also the trie strategy which not only will sort the strings, but will also reduce the space requirements for storing them and will have O(1) search behavior to boot...

[cork]

The problem is still not fully specified. How much extra memory (including both stack and heap) would be afforded?

If we get a few people interested, then that group can decide the rules of the contest.

My preference would be to use all the extra memory that you want and have the focus entirely on speed.

I'd prefer it to be simple. Initially you're given a 100 MB file of random length strings, zero terminated, UTF-8 or UTF-16 unicode, length from 5 to 40 characters long. Use as much memory as you want. We'll have to decide on a reference processor on which the final judging will be done.

Cork

[oex]

Hey Cork,

I think the problem here is as Hutch said 'it's been done before'.... For specific and needed sorts it's worth putting them in the laboratory but a quick search on google will come up with a large array of algorithms for multiple sorting purposes.... The hardest part with creating a competition like this is understanding the subject well enough to enable you to set fair and worthwhile parameters

Creating random competitions without a baseline takes the fun out of it a bit.... http://sortbenchmark.org/

If you're up for a challenge there is a good ongoing one on compression here: http://prize.hutter1.net/

or there is always the more commercial challenges like: http://en.wikipedia.org/wiki/Eternity_II_Puzzle :lol.... I'm sure this would benefit from a few good algorithms