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.

Re:Radix Sort

[Anonymous Coward]

How is this different from Radix sort?

Marketing.

animation

[hansamurai]

Let me know when there's a video on Youtube of the sort doing it's thing with colored bits and animation.

Re:FROTHY PISS

[Anonymous Coward]

No.
You are an "HTML programmer".
An oxymoron and a moron, simultaneously.
Defenestrate yourself.

That doesn't matter!

[Anonymous Coward]

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

[aprosumer.slashdot]

You're making the baby Knuth cry. Please read "The Art of Computer Programming" before proceeding any further.

Re:oh really?

[Ossifer]

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

Re:Did KD set this guy up for ridicule on purpose?

[remahl]

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.

Re:It's radix sort.

[Anonymous Coward]

Who do you thinks going to get the credit when they finally invent fission? The person who thought it up or those that actually made it?

The person who patented it, of course. :P

Re:How is this not a radix sort?

[Sillygates]

My favorite is still: http://www.dangermouse.net/esoteric/intelligentdes ignsort.html [dangermouse.net]

Sorts in O(1) and uses no memory!

How many stupidities in one post?

[Lord Duran]

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?

Re:The algorithm belongs to PhoenixBit and VirusFr

[maxwell demon]

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" :-)

Re:It's radix sort.

[rosscoe]

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.

Re:Only lists of integers

[StikyPad]

Does nothing for strings

ahhiiinnoooprrssssttt [wordsmith.org]

Re:That doesn't matter!

[ScrewMaster]

No difference ... he's just saying that you can have his Virus ... Free.

Re:It's radix sort.

[Lon]

my sort goes to 11 ... wait, that is only three :(

Knuth vol 3 page 173

[CustomDesigned]

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!

Re:I nominate this...

[DrMindWarp]

It's only March. There'll be an inventor of the internal combustion engine along shortly.

I'm not really sure, but.

[Goaway]

Maybe this guy has re-invented radix sort? I can't really tell! I wish somebody would post and tell me!

Re:Apropos

[asylumx]

"Those who cannot remember the past are doomed to repeat it." - George Santayana

Quoting Knuth...

[Ellen Spertus]

cartoon about Knuth [xkcd.com]

Re:How is this not a radix sort?

[Dirtside]

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!