Sort Linked Lists 10X Faster Than MergeSort 326
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.
How is this not a radix sort? (Score:5, Informative)
That doesn't matter! (Score:5, Funny)
Re:That doesn't matter! (Score:5, Funny)
Re: (Score:2)
Re: (Score:2)
Re:How is this not a radix sort? (Score:4, Funny)
Sorts in O(1) and uses no memory!
Re:How is this not a radix sort? (Score:4, Funny)
Re:How is this not a radix sort? (Score:5, Informative)
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 [codercorner.com].
Re: (Score:3, Interesting)
Funny, all I saw on the "site" was a donation link or something. Looked like a parked domain or something.
But radix sorting is cool. What is very relevant to it in 2007 is that it scales superlinearly with multiple cores/CPUs which is important since most computers today have hardware that execute multiple threads simultaniously.
It's radix sort. (Score:5, Informative)
Re:It's radix sort. (Score:5, Insightful)
radix is not
I agree though that the concepts for both algorithms are very similar.
Re:It's radix sort. (Score:5, Informative)
Re:It's radix sort. (Score:5, Insightful)
Well, I'm not sure, but I'm pretty sure it's not going to be the guy who made it again 30 years after everyone was already using it.
Knuth vol 3 page 173 (Score:4, Funny)
Quoting Knuth... (Score:3, Funny)
Re:It's radix sort. (Score:4, Funny)
Re:It's radix sort. (Score:5, Funny)
Nice, but... (Score:2, Informative)
Re:Nice, but... (Score:5, Informative)
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: (Score:2)
That's
Re: (Score:2)
Re: (Score:2)
Only lists of integers (Score:3, Informative)
Re:Only lists of integers (Score:4, Interesting)
Re: (Score:3, Funny)
ahhiiinnoooprrssssttt [wordsmith.org]
radix sort vs. comparison sort (Score:5, Informative)
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 (Score:4, Interesting)
Re:radix sort vs. comparison sort (Score:5, Informative)
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 (Score:5, Insightful)
Damn you! You made me look at his code! The goggles, they do nothing.
I can't help feeling he should have declared Ptrs and Tails as Node* arrays, and bypassed all that random casting to longs. Not sure what's going on there. 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.
At first, I thought it wasn't a stable sort, but looking further into it, that's because he mixed up the 'head' and 'tail' descriptions in the explanation (or possibly in the code).
It is amusing that some /. posters think that doing this in-place is somehow an amazing leap of insight. Sometimes /. is like reading thedailywtf.com - you see something dumb as the main story, and then find half the people commenting on it have even less of a clue.
I must be new here.
Re:radix sort vs. comparison sort (Score:5, Informative)
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]) {
(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: (Score:3, Interesting)
I don't know if you're still interested, and I'm just hypothesizing here, but 0xFFFF is 65535 and some other posters noted that his array was of size 65535, which of course means that index 65535 is out of bounds by just one. This could cause your segfault.
HTH,
Kig.
Re: (Score:3, Informative)
Unfortunately this followup will forever be buried below the mod threshhold but it appears that des
Ripping apart the source (Score:5, Informative)
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.
Re:radix sort vs. comparison sort (Score:5, Informative)
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. (Score:5, Informative)
Tom
Re:wtf? seriously. (Score:5, Insightful)
Sixth, the headline "10X faster" is incorrect, as they differ asymptotically, not by a constant factor. (Run different data sets...vary by size of a single element, and by number of elements in the list. The ratio will change.)
Re: (Score:3, Insightful)
Re:wtf? seriously. (Score:5, Insightful)
It would require a software patent to restrict the use of the algorithm to GPL programs.
(And sixth, a quick look in a text book would have clued the author in)
Re:wtf? seriously. (Score:4, Informative)
Provably impossible, in fact.
I'm not sure that's a fair generalisation. There are several good O(n log n) sorting algorithms, heap sort being another obvious one, and typically things like the data structures involved, need for stability, or ease of parallelisation are the deciding factors in practice. In fact some of the best performing algorithms in real terms are theoretically O(n^2) in the worst case, hence the creation of hybrids like introsort, a quicksort variant designed to avoid the worst case by switching to heap sort after a certain recursion depth is reached.
Anyway, I'm afraid this is another article by a 21-year-old student who is well-meaning, but not nearly experienced enough yet to appreciate that his suggestion is just rehashing (no pun intended) a lot of long-established ideas. I think the giveaway sign is that his CV on the site still lists just about every programming language and web development skill in existence. :-)
Re: (Score:3, Insightful)
Third, merge sort is O(n log n) time, hard to beat for random data.
Provably impossible, in fact.
Not quite. O(n log(n)) is only the best case for comparison-based sorting. That is, if you have a less than (or greater than) predicate, you can build an algorithm that is O(n log(n)) using it. If your algorithm is not comparison-based, you can beat O(n log(n)). The most obvious example is bucket-sort, where you have k possible values. You pass over your list once, placing the value in the correct bucket, which gives you O(n) performance, at the cost of requiring k buckets worth of storage space (you
Re: (Score:3, Interesting)
Agreed. For example, in a microcode example at work, the cost of searching for a given string was totally dominated by memory access time, so it really didn't matter which algorithm we used. So we used brute force. Pretty easy to debug, as well.
Re: (Score:2)
For comparison searches, O(n log n) is not just hard to beat it is IMPOSSIBLE to beat.
See http://www.ics.uci.edu/~eppstein/161/960116.html [uci.edu].
Of course, radix sort is not a comparison sort, but has its own limitations as others have noted.
And Quicksort technically has a O(n^
Re: (Score:3, Informative)
As a plus, merge sort requires no recursion, which may be helpful if your stack is really tiny, like 200 bytes large.
Re: (Score:3, Informative)
Re: (Score:2)
Now, there is the question of whether you want to do it, but you most certainly can. For my unsigned integer linked-list sorting needs, I've found radix sort with a radix of 6 to work pretty well in prac
Re: (Score:2)
10X speedup? Compared to what? (Score:2, Insightful)
Linear improvements are completely uninteresting. Take algorithm X in Perl, then a version in optimized assembly, and there you go, a 10X improvement without having done anything groundbreaking.
A 10X faster bubble sort is just as useless for large enough values of n, and a 10x slower merge sort would still have a very good performance in comparison.
Nice try, b ut... (Score:5, Informative)
It was used by 80-col card sorters, since circa 1925.
See Knuth, Volume 3
Re: (Score:2)
Re: (Score:2)
You might like to know that the above domain (which I assume is yours from the DNS registration) seems to have been parked.
Knuth-h (Score:2)
multithreaded merge (Score:2)
Re: (Score:2)
Re: (Score:3, Interesting)
Re:multithreaded merge (Score:5, Informative)
Re: (Score:3, Informative)
Re: (Score:2)
There are entire classes of sorting algorithms for multiprocessor machines, including algorithms optimized for shared versus non-uniform memory architectures, message passing, sortin
Re: (Score:2)
animation (Score:2, Funny)
Re: (Score:2)
And just as unscientific...
Can't believe I wasted my time (Score:2)
Against my better judgment, I skimmed the article, code.
Two observations:
Why no analysis of impact on memory usage? 10x speed-up, but at what cost? Omitting this detail makes it difficult to weigh the utility of the algorithm.
Not an Apples to Apples comparison. In the source, the "BitFast" sort converts the entire link-list into an array before performing the sort. Without even considering the merits of the actual algorithms, the Mergesort has no chance of being faster given the more complicate
You're making the baby Knuth cry (Score:5, Funny)
Re: (Score:2)
Time for the "reinventthewheel" tag? (Score:2)
How about "badcomputerscience"?
GPL-ed algorithm? (Score:3, Interesting)
Please correct me if I'm mistaken, but this seems like a fairly bad precedent to set.
Re:GPL-ed algorithm? (Score:5, Informative)
Re: (Score:2)
Re: (Score:2)
No textbook would want to include GPL-ed code--wouldn't that make the entire book GPL by nature of the license?
Not as long as you provide the source (which of course you would; it's the whole point) and don't impose any additional restrictions on the license. If you modify GPLed code, then you have to release the revised source if you distribute the binary.
That said, a lot of nonsensical FUD has been circulated regarding the requirements of the GPL by parties who feel their interests are threatened by it. As with everything, it's best to read it for yourself.
Did KD set this guy up for ridicule on purpose? (Score:5, Informative)
- 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.
Re:Did KD set this guy up for ridicule on purpose? (Score:4, Informative)
Re: (Score:3, Funny)
Re: (Score:3, Interesting)
solution in search of a problem (Score:5, Insightful)
This is a variant of RadixSort, which is well known to be faster than any comparison sort such as MergeSort. The problem with non-comparison sorts is that as such they are restricted to sorting items representable a unstructured bit fields, which means, essentially, integers. A large part of the time, the real problem in sorting is (a) extracting the fields that you want to use as keys (since it is not generally the case that you want to sort on the entire record) and (b) arranging for each pair of records to compare as you need them to, which involves both recognizing the internal structure of keys (consider the case of dates) and imposing suitable weights for the individual components. In other words, in many situations the bulk of the code and time are devoted to parsing and transformation of records. So long as you are not using a really bad algorithm, the time devoted to the sort itself is likely to be a small percentage of the total time.
For example, I have written a sort utility [billposer.org] that differs from most others in its ability to parse the input into records and records into fields and in the transformations it can apply so as to use unusual sort orders and sort on things like dates, month names, and numbers in non-Western number systems. It was originally written for alphabetizing dictionaries of "exotic" languages. It is frequently the case that the time devoted to the actual sort is less than 1% of the run time.
In sum, non-comparison sorts have a niche but are of limited utility because they get their speed from making use of additional information that is only available for a limited set of datatypes. For the great majority of applications, only comparison sorts are flexible enough to be of use.
Re: (Score:2)
While radix sorts are limited, binned sorts, which are a superset of radix sorts, are more powerful. Binned sorts do work on a broad set of data types, but you have to use statistical techniques to dynamically pick a good distribution among the bins. SyncSort [syncsort.com] developed this technique in the 1960s, and had the first software patent, now long-expired. Mainframe batch systems have used such techniques for decades.
The general idea is that if you're sorting, say, text strings, you watch them go by for a whi
Re: (Score:2)
No, it isn't a database. It doesn't support queries or allow for the insertion or modification of data. A true statement would be that the sort functions of database management and query programs are usually closer in flexibility to msort than are stand-alone sort utilities.
His algorithm :::is::: optimal (Score:2)
Shock horror, stop the presses (Score:3, Informative)
Also manages to not know about memset and write C code that assumes sizeof(long)==4 and puts non-inline code in header files. I don't dare look at the C++ code since there's a large probability it will cause permanent brain damage.
Re: (Score:2)
Chapter and verse please. Where in the C Standard does is that stated? sizeof(long)>=4 is what I recall. Of course historically (and for compatibility with code written by people who don't care about portability) sizeof(long)==4 is the norm. sizeof(long)==8 is what makes sense for 32 bit machine. After all sizeof(int) will be 4, but due to those aforementioned programmers it never is...
Where's the proof? (Score:2, Insightful)
Where's the proof?
Is it peer reviewed? Has it been published? Does it exist?
Although the lack of a proof does not make your algorithm is incorrect, I'd be suspicious. In fact, I would be unwilling to use any algorithm in my code without being sure that a good proof of its correctness exists somewhere.
Proofs are more than formalities, they're essential: without a good proof, you're just a crank sellin
Buffer overflow (Score:2, Insightful)
The code in "BitFast" then uses the array as if it can access Head[0xffff] and Tail[0xffff] - which is one past the end of the arrays. I'd guess it works by coincidence on Win32.
Additionally, although there might be some reason I can't follow at the moment, in the float version only the top 15 bits of the value
How many stupidities in one post? (Score:2, Funny)
Invented by George Papadopoulos (Score:2)
Please be kind to this kid (Score:2)
I am not saying he is Ramanujan [wikipedia.org] or anything like that. But still every amateur deserves to be forgiven once.
Re: (Score:2)
Memory leaks... (Score:4, Interesting)
long *Tail = new long[65535];
long *Head = new long[65535];
for(n = 0; n < 65535; n++){ Head[n] = 0; Tail[n] = 0; }
Memory leak of 128KB for each time the function "Node* BitFast(Node* HeadNode,long run)" is called.
MISSING: delete[] Tail; delete[] Head;
Furthermore the following is faster or use memset:
long Tail[65535] = {0};
long Head[65535] = {0};
Unless you are running this in DOS16, DOS32 with Pharlap or smaller 8051, 68000 processor, you do not need to use new[] or malloc() for this.
In InsertToList, Node *tmpP = (Node*)malloc(sizeof(Node));
free(tmpP) missing inside FreeList()... no such function
In main.c:
Node *L1 = malloc(sizeof(Node));
Node *L2 = malloc(sizeof(Node));
MISSING: free(L1); free(L2);
In main.cpp:
Node *L1 = new Node;
Node *L2 = new Node;
Instead use (no need to use heap, use stack memory):
Node L1 = {0}, L2 = {0};
Mixing the usage of std::cout and printf() is not recommanded.
Use all of the former or the later, else you will have weird display on some run, unless you flush the output buffer. I suggest you use printf() all the way.
cout << "Ok!!!!" << "\n\n" << "Merge Sort : " << tim1 << " ms\n" << "BitFast : " << tim2 << " ms\n\n";
becomes:
printf("Ok!!!!\n\nMerge Sort : %ld ms\nBitFast : %ld ms\n\n", tim1, tim2);
Furthermore, your implementation of link list, and calling Length(Node*) for every equal is highly inefficient, requires O(n). Store the link list length somewhere when inserting. EqualSplit takes O(1.5n) instead of O(0.5n) because of that.
Something like:
typdef struct LinkList {
Node head;
int length;
} LinkList;
As a result, MergeSort recursively call itself, which calls EqualSplit every turn.
You should make your header file C friendly, and avoid mixing
No clue why this header is needed:
#include <iso646.h> instead of not/and use use ! and &&
before: if(not p) return NULL;
becomes: if(!p) return NULL;
Finally, BitFast is not recursive; therefore, you should try to find an implementation of merge sort which is not recursive also, so you save on function calls, if possible.
"However, iterative, non-recursive, implementations of merge sort, avoiding method call overhead, are not difficult to code." -- Wikipedia
http://en.wikipedia.org/wiki/Merge_s
Your function should be in a file.c or be inline.
Not possible... (Score:2)
withing a factor of two, as long as general purpose CPUs are used.
It seems this is an O(n) algorithm, of which there are two: Bucket-sort and Radix-sort. No other ones are possible. These are better in theory and practice, but have limited applicatbility. i.e. do not work for all input data. Merge-sort is an universal sorting algorithm.
Multiple bugs in the code, wrong measurements ! (Score:5, Interesting)
First, there are multiple bugs in the code itself :
1) everywhere, it is assumed that 2^16 = 65535 and not 65536. Arrays are allocated for this size too, but are used with 65536 entries. (un)fortunately for him, the space is probably allocated anyway so the program does not crash on this.
2) a similar bug in the random number generator carefully avoids dangerous values, because he generates numbers between min and max by doing a modulo on max-min , which prevents max from being produced. This is not a
big deal anyway, just that it hides the bug.
3) he assumes everywhere that "long" is unsigned and "short int" too. This makes the code SegFault on Linux with negative array indexes. The fix is obvious, though.
And most of all : times are measured in optimal conditions. Indeed, this algorithm is
just a radix sort with a large radix (2^16). A radix algorithm is efficient when the number
of elements is high compared to the radix, because at every level, all radix entries have to
be scanned for existing values. In his example, he sorts 4 million elements. His code is faster
than the merge sort on 4 million entries, just as would be any radix sort. But on smaller sets,
it still takes the same time per level, because it has to scan all 65536 entries even if there
are only 100 numbers. The fact is that for less than 10000 values, the mergesort becomes faster in his own code.
When measuring algorithms complexity, we use the O(x) notation. The time per iteration is never
considered. When the time matters (as in his example), we should consider the time per iteration (T), and the total time (t) will follow
t = T . complexity
In complexity, his algorithm is O(N) on 16 bits, but the time per iteration is very high. Other sorting algorithms are O(N.log(N)). So the total time is :
t1 = T1 . O(N) for his algorithm, and :
t2 = T2 . O(N.log(N)) for the mergesort.
But when T1 > T2.log(N), he looses, which is almost always because log(N) is small for 16 bits, and T2 too because operations are very simple. In his case, T1 is very high because it represents the time required to scan 65536 values.
It's amazing that he fell in such a beginner's trap. I suppose that he's still a student, which would explain the total lack of portability and newbie's bugs in the code.
Well tried anyway
Willy
Re: (Score:3, Informative)
This examples are for Proof of Concept only.
They are not the most error free,optimized,commented,beautifull code
to have ever been written
Personally I would never write code like this, proof of concept or not, avoiding the portability problems for example would not have taken more time to write. But pressumably more experience. So probably the best thing to do is be constructive about it.
I'll give it a shot on some of the issue
I'm not really sure, but. (Score:4, Funny)
A couple of non-obvious notes about radix sort ... (Score:3, Insightful)
1. Although it's technically O(n) compared to QuickSort's O(n log n), consider the fact that
a. the number of passes required by radix sort is proportional to the key size, and that
b. if the keys are primarily unique, then the key length will be O(log n)
2. One cute feature of radix sort for very large data sets is that you only need linear access to the data, so it can be done with non-random-access external storage. The one practical implementation I've ever heard of used four 9-track tape drives.
However, considering use in main memory, both radix sort and quicksort make efficient use of a D-cache that is 2-way set-associative or better, and both hit the whole data set once per pass -> if it swaps, it'll swap a lot
Re:Radix Sort (Score:5, Funny)
Marketing.
Re:FROTHY PISS (Score:5, Funny)
You are an "HTML programmer".
An oxymoron and a moron, simultaneously.
Defenestrate yourself.
Re:FROTHY PISS (Score:5, Insightful)
As for the quality of your post: let me guess--you also complain about slow, bloated software, right? The old, "Intel giveth, Microsoft taketh away," adage? Users have several orders of magnitude more compute and storage power than 'back in whatever day' yet personal computers seem little more responsive, etc.
Don't feel lonely. There's a large population of lugnuts like you, who, if they think of CS at all, largely carp about how some CS departments haven't become current technology de jour tradeschools. Some, unfortunately, have, but that's a whole different discussion, which has been seen on Slashdot time and again.
Algorithm research is important, as is having at least something of a grasp of algorithms. In *your* next programming exercise, since you seem to regard sort efficiency as 'esoteric', feel free to reinvent the bubble sort. Also, tout it as the Next Great Thing, and submit patches against all your favorite apps. That will get you your twenty seconds of fame, I assure you.
Sometimes I love Slashdot--but then I read a post from some random AC idiot like you: the proverbial lowest common denominator. Maybe you should restrain your efforts toward what you seem to regard as cool snarky posts, watch a thread (about which you plainly know nothing) develop, and maybe freaking *learn* something.
OTOH, maybe I'm just bitter right now, because I've just been doing a search through Google news on climate change, and I'm pretty much convinced that the last thing the human race needs right now is people like you.
Re: (Score:3, Funny)
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, sur
Re: (Score:2, Insightful)
Quicksort may have a best expected sorting time, but still has an O(n^2), since O is worst case. I think the STL takes a pass at the list to determine how sorted the list appears to be and then picks a sorting algorithm based on that... but it's bee
Re: (Score:2)
Please give me running time in Big O notation [wikipedia.org].
Oh, but he says he didn't want to go into a bunch of theory. In other words, he doesn't understand the theory. In addition to theory, add copyrights and patents to the list of things he doesn't understand:
1. You release the code under the GPL, not the algorithm. 2. You don't 'own' the a
Re: (Score:2, Insightful)
No. Quicksort is O(n log n) on average. There are pathological scenarios, but all other instances absorb the O(n^2) worst case. Sedgewick's PhD (under Knuth's) was about Quicksort, try reading it if you are nuts enough. Or even read Knuth's volume on sorting, to see hem distilating and comparing even the constants from the algorithms.
Re: (Score:2, Interesting)
Messy and inconsistent indenting (check c/ and c++/ files for differences)
Difference between c/* and c++/* is that c++/ has cout instead of printf()... well done...
This stuff should go to worsethanfailure.com (was TheDailyWTF.com)
Re:The algorithm belongs to PhoenixBit and VirusFr (Score:2, Funny)
Re: (Score:3, Funny)