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

Re:How is this not a radix sort?

[acidrain]

This algorithm is exactly how my first year comp-sci teacher taught radix sort. I'm guessing "VirusFree" stole his lecture notes.

It's actually much cheaper to use arrays of indices or arrays of pointers internally instead of linked list operations, but "BitFast" is a good naive implementation if you don't wasn't to confuse first year comp-sci students who only just learned about linked lists.

Here is a good paper of radix sort optimization, and it covers using radix sort with floating point.

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:radix sort vs. comparison sort

[Wavicle]

But then anyone who thinks the roundabout way he used of accessing the top 16 bits of a 32-bit memory value is 'cool' is definitely on my list of people most likely to re-invent the radix sort badly.

It is clearly a slow day for me. I have gone one step further and ported his code over to Linux (only required a change to GetTickCount) and attempted to run it. His "cool" way of using a pointer hack has caused his code to dump core. The problem is his hack being a signed short int pointer.
Program received signal SIGSEGV, Segmentation fault.
0x08048752 in BitFast (TailNode=0x804a018, run=0) at bitfast.h:37
                    if (Tail[val]) { //if not 0
(gdb) p val
$1 = -22087

So I try putting unsigned on ptrHack.
Program received signal SIGSEGV, Segmentation fault.
0x08048772 in BitFast (TailNode=0x804a018, run=0) at bitfast.h:39
                    tmpN->nextNode = pN;
(gdb) p tmpN
$1 = (Node *) 0xffff
Yeah. Not so sure that casting is what he really wants. I'm not entirely clear how it is his code will work. I really wanted to clean up his mergesort and re-run it to see how valid his claim is, but it looks hopeless. I'll work on it a little more, but since the problem seems to be in his algorithm, it doesn't look real hopeful.

Re:radix sort vs. comparison sort

[adrianmonk]

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.

That is maybe a bad implementation, but it actually does not make it O(n^3). In fact, it doesn't make it as bad as even O(n^2). Here's why:

The first thing I want to establish is that linearly iterating halfway through the sublist a second time (to find the middle of it) has no effect on the asymptotic analysis. It just means going through the sublist 3/2 times, which is still a constant.

The second thing is this: as you go deeper and deeper into the recursion, the size of the sublist is repeatedly cut in half. Thus, at every level as you go deeper into the recursion you are doing twice as many loops as the previous level (one loop for the first level, when the sublist equals the original list; two loops for the second, when you are breaking halves into quarters; four loops in the third level of recursion; and so on). BUT, although you are doing more loops, the size of the sublist is always half what it was at the previous level of recursion. So have you twice as many loops but half as many loop iterations.

That means at every level of recursion (think of this size of the call stack if that helps in visualizing it), you are looping over the entire list once (well actually 3/2 times). And there are O(log n) levels of recursion, because every time you recurse, you are working on a list half as big as before.

The result is that the total extra added time of this unnecessary linear traversal is O(n * log n) for the entire algorithm. Since mergesort is already O(n * log n), the extra looping to find the middle and end of the list has no effect on the asymptotic behavior of the algorithm.

wtf? seriously.

[tomstdenis]

First, it's just a radix sort [well that's my take]. Second there are too many google ads on that page. Third, merge sort is O(n log n) time, hard to beat for random data. Fourth, most people use variations of the QUICK SORT not merge sort.

Tom

Nice try, b ut...

[Ancient_Hacker]

I think you may have re-invented the "radix sort".

It was used by 80-col card sorters, since circa 1925.

See Knuth, Volume 3

Re:multithreaded merge

[TERdON]

I have studied a course in parallel algorithms, including localized parallel merge sort (the algorithm you requested). It can be used to subdivide parallelized sorting theoretically unlimitedly. Links: Course homepage, The relevant chapter (PDF) of the course slides, with nice pictures and everything.

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.

Re:GPL-ed algorithm?

[Helios1182]

You can't copyright an algorithm, so there is no license to worry about. This is a well meaning but utterly clueless person who reimplemented a well known algorithm and then made a strange constant-factor instead of asymptotic analysis.

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.

Ripping apart the source

[jinxidoru]

The previous few posts caused me to also open up the code. Wow! What a ride! I decided that I wanted to add a few things I found as well.

I loved that he referred to his use of the short pointer as a "cool pointer hack to avoid shifts and ifs!!!" To begin with, if we have to call that a "cool hack" then the requirements for coolness have definitely dropped a bit. I am also confused as to how this helps avoid shifts and ifs. As far as I can tell, it avoids one shift. I'd love to see the code without the "cool hack" because I'm intrigued as to how he uses an if statement to remove the higher bits.

As stated before, I am also fond of his use of an array of size 65535 rather than 65536. I surprised he didn't run into any segmentation faults. I know that I can give him a test case that will seg fault pretty easily.

I also question whether he understands the purpose of a header file, as the entire source for his BitSort is contained within a header file. I guess it would sort of make sense if the function was declared inline, but it isn't.

Another fun element is how non-modular his code is. Everything is hard-coded, even though it would have been easy to declare a few constants or even make the function a template.

Lastly though, why the crap did this article get through the editors. It is, as has been stated over and over, a radix sort and nothing different. I know that he claims it is different because it is in-place, but that is such an obvious simple change that it does not warrant a whole new algorithm. Regardless of the content, the article is so poorly written with some of the worst grammar I have read in quite some time. Slashdot really needs to improve its article standards.