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.

Comments

How is this not a radix sort?

[Anonymous Coward]

http://en.wikipedia.org/wiki/Radix_sort

It's radix sort.

[Nick Mathewson]

From the page:

4. Logic of BitFast BitFast works with numbers in the bit level. It applies masks to cut the numbers so it uses only the desired ( based on the programmer/problem specifications ) number of bits every run. It always start with the LSB ( Less Significant Bits ) ignoring the any other bits and every run it moves to the higher block of bits until the whole list is sorted. So is we want to sort 8 bit every run , the first timer it will sort 0-7 bits ( Least significant ), then the 8-15 bits , then the 16-23 bits and for last the 24-32 bits ( Most significant ) , having now sorted the entire list of 32bit numbers

Congratulations, you have reinvented radix sort.

Re:It's radix sort.

[vidarh]

Making it in place is just an implementation detail, just as most other sorts can be done either in place or not (a typical example is quicksort, where most naive implementations tends to copy, while the typical C implementations tends to be in place).

radix sort vs. comparison sort

[Peter Desnoyers]

It's a bit of an apples vs. oranges comparison to put this up against mergesort - mergesort is a comparison-based sort, while Papadopoulos' bitfast is a radix sort and thus O(N*W) where N is the number of elements and W is the width of each element in bits. (hint - try sorting 1000-byte strings with bitfast, and see which is fastest) And no, it doesn't have anything to do with hashing.

However, it's definitely a clever way of implementing radix sort with linked lists, which may make it useful in some cases (e.g. OS internals) where you don't want to allocate space for a big directly-addressable array.

Re:radix sort vs. comparison sort

[Wavicle]

Actually it is much worse than you say.

I don't know what possessed me to look at his code, but he really hasn't shown what he claims to have shown. It isn't clear to me that his code is doing what he says, but what IS clear to me is that his comparison to mergesort is very unfair. He has a TRULY AWFUL implementation of merge sort. For example, every time he goes to split a sub-list in half, he does a linear search from the current node to the end the sub-list. Having determined this value he then does ANOTHER LINEAR SEARCH to find the half-way point.

So he has basically made an O(N^2) time complexity process just to divide the list for the merge sort. This is inside his n*log(n) merge sort. So he has an O(n^3) time complexity mergesort and trumps up how fast his modified radix sort is. Come on! Bubble sort would have beat his mergesort.

His cleverness gets the better of him when it comes to his modified radix sort. For example, he creates two arrays (on the stack) of 65535 elements; apparently unaware that this creates an array with indexes 0..65534.

Re:Nice, but...

[dlthomas]

I guess it technically *is* O(N * log(N)) to the number of items, but this is misleading. It's actually O(N).

As pretty much everyone has pointed out, it's just radix sort. The time taken by radix sort scales linearly to the number of keys, and with the log of the maximum key that can be held by the container.

If we're dealing entirely with unique keys, this is of course >= log(N), by the pigeonhole principle and all that. If we may have duplicate keys, however, there may be more keys than container space, and radix *does* scale linearly to the keys.

Time to prepare and overhead of this alrogrithm are negligable in any context large enough for us to care about the O() of the algorithms. For some things, this *is* better than mergesort. I'm just not sure why it was posted, as it's also not new - it was invented over 50 years ago.

Did KD set this guy up for ridicule on purpose?

[grimJester]

Ok, I'll start from his site:

- Programming Skills : Visual Basic ***Excellent***

Yes, that certainly is... excellent.

- Message : "Don't ever let school, stop you from learning!"

School could, learn you some grammar.

The algorithm is being released under the GPL ( General Public License ). The algorithm belongs to PhoenixBit and VirusFree but you may use/modify it freely.
*** DO NOT COPY ANYTHING FROM THIS PAGE TO ANY OTHER PAGE. IF YOU WANT SOMEONE TO READ THIS THEN LINK TO THIS PAGE ***

In addition to trying to apply copyright to an algorithm, doesn't a restriction on copying defeat the purpose of releasing something under the GPL? Or does text in all caps trum previous text not in all caps?

Feel free to add to this. If there are some clips of this guy with lightsabers, pleas post them.