A description of Beechick sort (also known as ABCsort, an acronym for Allen Beechick's Character sort) follows, explaining its advantages over the quick sort algorithm and other sorting algorithms. If you get Beechick sort, you will get the DLL which contains the sorting algorithm, along with sample test scripts in C++ and sample files to sort.
BeechickSort (patent 5,218,700) has these characteristics:
How is Beechick sort different from other computer sorting algorithms?
Most other sorting systems use compares. Beechick sort does not. Whether it's bubble sort, insertion sort, merge sort, shell sort, selection sort, heap sort, tree sort, or quick sort, they all try to optimize compares, and their uniqueness lies in the way that they handle compares. But Beechick sort bypasses that altogether.
If it doesn't use compares, then how does it sort?
This is a radix sort. It puts the As in the A bucket, the Bs in the B bucket, and so on. Then it continues with the next digit until only one is left in a bucket. When you put your socks away in the dresser drawer, you don't compare drawers until you find the right one. (Whoops! This is the shirt drawer - I have to move up one!) No, you go directly to the correct drawer. This sorting algorithm puts the keys directly into the correct bucket.
How is this different from other radix sorting algorithms?
Other radix sorting methods start with the least significant digit (the end of the word). This one starts with the most significant digit (the front of the word). The old radix sorting method needed to examine each and every digit. But this radix method examines only as many digits as necessary in order to determine the uniqueness of the key, making it the fastest sorting method of all.
Why doesn't it eat up memory?
The memory roadblock prevented Knuth from arriving at a most significant digit radix sorting solution. He said, "The multiplicity of the piles becomes confusing." If we allowed the piles to multiply, it would eat up memory prohibitively. But instead of multiplying piles, this sorting system economically organizes piles to keep them to a minimum. Therein lies the solution and the secret.
Why don't you sell the algorithm to Microsoft?
I tried. That was before I got a patent. They said I would never be able to patent it, because they said it was just like other radix sorting algorithms, and they were not impressed with it. But the patent office saw the uniqueness of this sorting algorithm.
Does it sort numbers?
Yes, if you treat numbers as text strings. Since the algorithm examines digit by digit, it is suited best for text.
What affect does a longer list have on the sorting time?
Unlike other sorting algorithms, a longer list does not exponentially increase sorting time. The increase in time is closer to a linear increase.
Why don't you give it away for free?
The patent attorney didn't do his work for free. The government patent office didn't grant the patent for free. So it would be nice to get back at least some out-of-pocket expense.
This excerpt from the patent describes the uniqueness of this computer science sorting method:
The present invention is not a new twist on this old method, but it is an entirely new way of sorting using the computer. Instead of using compares, the present invention categorizes words according to letter.
The result is a dramatic reduction in time that the sorting process requires. The longer the list, the greater is the percentage of time that is saved. Since this invention does not use compares, it has no formula to calculate the number of compares. However, there is a formula which approximates the number of sorting operations, a sorting operation being defined as looking at a word and placing it into a category. The formula is N × log(base x)(N), where x is the range of values that individual characters can take, such as 26 for alphabetical sorting, or 10 for numerical sorting, and where N is the total number of words in the list to be sorted. This formula approximates the number of sorting passes, because lists may have words clustered in unpredictable configurations. For example, a list may have an over-abundance of As and an absence of Zs. In the event of such configurations, the number of sorting operations will be somewhat more than the formula approximates, but it will still be far less than prior art has been able to achieve. The very fact that prior art uses formulas with log(base 2) and this invention's formula uses a log with a much higher base shows that it saves time in exponential increments.
My colleague, Lynn Yarbrough, who has developed implementations of this algorithm called ABCsort (an acronym for "Allen Beechick's Character sort"), says that the correct argument in the patent should have been:
The algorithm is linear in speed: it examines each character in the file AT MOST ONCE, so there is no logarithm in any of the formulas; the algorithm is O(N) in both space and time.
You will receive a zip file containing:
Call the Beechick sort function in a manner similar to how you call the quick sort function. Both have parameters to pass. Both pass a pointer to the list being sorted. But there's a difference. Whereas quick sort needs a parameter pointing to your compare function, Beechick sort does not use compares. Instead it uses a pointer to your output function. When I say output function I mean the function that directs the sorted results to the screen, to a file, to memory, or to whatever. This output function receives sorted results not all at once at the end, but rather it receives sorted results one by one as the keys are being sorted. This makes the top results available seemingly instantaneously.
So the Beechick sort output function replaces the quick sort compare function. You will see examples in the sample test scripts.
You get all six files listed above, including the fully functional DLL. In addition to these six files, you also get the commented C++ source code behind the DLL. Beechick sort must prove at least twice as fast as quick sort, or you get your money back. You can have yours in a couple minutes.