Here is a challenge of another sort. Who can write the fastest sorting algorithm?
I post here because I know this is a good place full of smart people who like a challenge, many of which are also programmers. I have searched the internet and never come across anything that really was fast for what I was interested in. I attempted this challenge about a year ago and came up with an algorithm that I feel is pretty fast, it is about twice as fast as an optimized quick sort, and its the fastest I've found for sorting things of size 10,000 to 100,000,000 on regular computers (not that it would be slow for things bigger, but I have only tried to make it for in memory sorting). Now I'm not here to brag or anything, I'm here to get a challenge and to see if my algorithm can standup to other's speed.
For this challenge lets say fastest sort algorithm to sort 10,000,000 uniform random positive integers from 0 to 2^31. Feel free to take advantage of that fact that its uniform distribution, I did, but I think it would preform pretty well on non uniform also, I haven't tried yet. Things like bucket sorts would be theoretically ideal for this, but in practice they weren't that fast because they were basically consantly getting cache misses.
Now I'm not going to post the code for my algorithm yet, because if it actually is any good I might want to do something with it some day and not have someone else claim it as their own. But I will post the code used for timing it and provide an optimized quicksort for you to compare your algorithms against, since you can see how my algorithm compares against it:
xws:~/me/sort/new] darren% ./runsort darren 10000000
darren took 2.090000
[xws:~/me/sort/new] darren% ./runsort quicksort 10000000
quicksort took 5.100000
Here's the code to time the sorting algs
I know many computer scientist just say well aw its the same asymtotic behavior so what is the point? But for real world applications people care about run time. This run time varies from computer to computer but I compared this sorting algorithms along with others on several different machines and they were always roughly the same speed relative to each other. Also in my algorithm I use some function calls to mac specific stuff to load some memory while its doing other stuff, this improved overall speed by about 10% and this equivalent thing could done on most machines.
To add your own sort to this code. Write your sort of the form void sort(int *data, int length). Add this function into a new file or into the demo.c. Then in sort.c add the name of the function into the list like is done for quicksort and insertionsort. My code isn't much commented but everything that you need to know to use it is.
Good luck and feel free to post or private message any questions.
