Slashdot Mirror
Sort Linked Lists 10X Faster Than MergeSort
virusfree tells us about a new algorithm that has been developed that the author claims can sort a linked list up to 10 times faster than MergeSort. "BitFast," a member of the Hash algorithms family, is available in C and C++ under the GPL.
Marketing.
Let me know when there's a video on Youtube of the sort doing it's thing with colored bits and animation.
Reviewing just the first hour of video games.
No.
You are an "HTML programmer".
An oxymoron and a moron, simultaneously.
Defenestrate yourself.
This was written by VirusFree! Who wouldn't want to use something by a guy named VirusFree? It's a million times better than something by FreeVirus.
You're making the baby Knuth cry. Please read "The Art of Computer Programming" before proceeding any further.
> First of all, algorithm running times and complexities are not compared as 3x or 5x faster. Please give me running time in Big O notation. Saying 10 times faster than merge sort makes no sense.
But I came up with a sorting algorithm yesterday that's 12 times faster than bubblesort! Click here to see my advertisements....
Seriously, mergesort (but NOT quicksort) is optimal, O(n log n) in one model. But there are sub-n log n sorting algorithms in other models. Some of them are based upon radix sort, surprise, surprise....
I'll tell you what's ironic: People pointing out ironic things under the assumption they're not. That may make this message is ironic.
My favorite is still: http://www.dangermouse.net/esoteric/intelligentdes ignsort.html
Sorts in O(1) and uses no memory!
I fear the Y2038 bug
1. Loop ......................AddHobbie ("Computers"); ................Do Until 1=2
Since he says he's "**Excellent**" in Visual BASIC, one could ponder how he MIXED UP THE Do AND Loop STATEMENTS.
2. Don't ever let school, stop you from learning!
He apparently never had...
3. 10 times faster than MergeSort? That's asymptotically, right? O(10nlogn). Call the press. (Doesn't matter that Radix Sort actually takes O(n), as long as it's 10X!)
4. BitFast start by creating two arrays of size 65535 ( pow(2,16) )
Anyone got a calculator? Somehow his numbers don't add up. Is it actually possible for a positive power of two to be odd?
And...Since when do you use pow to calculate powers of two?
5. They are not the most error free,optimized,commented,beautifull code to have ever been written
Gee...really?
Of course one would hope that the patent examiners at least have heared about radix sort, and therefore would reject that patent due to prior art ... but then, maybe he can avoid that by adding "with a computer" :-)
The Tao of math: The numbers you can count are not the real numbers.
Wow, he uses the new 33bit ints as well, enabling numbers twice as high as the so-old-school 32bit ints and making it just that 'little bit' better.
Does nothing for strings
ahhiiinnoooprrssssttt
https://www.eff.org/https-everywhere
my sort goes to 11 ... wait, that is only three :(
The Art of Computer Programming, vol 3, Sorting and Searching, 1973, by Donald Knuth Page 173, Algorithm R - radix list sort. No credit is given. The algorithm has been well known and obvious since the first link list was invented. Hey! A good choice for a patent!
It's only March. There'll be an inventor of the internal combustion engine along shortly.
Maybe this guy has re-invented radix sort? I can't really tell! I wish somebody would post and tell me!
"Those who cannot remember the past are doomed to repeat it." - George Santayana
cartoon about Knuth
Pfft, everyone knows the best sort is random sort. Randomize the list. Is it sorted? If not, randomize it again! You'll hit it eventually!
"Destroy science and religion. Science would re-emerge exactly the same; but not religion." - Penn Jillette, paraphrased