This kind of bitwise MSD sorting is “sharpened" for strings. However, the algorithm is not so named for lexical specialization. Author Allen Beechick chose a name after himself, ABCsort stands for Allen Beechick Character sort .

Bichik himself is remarkable in that he is not only a programmer, but also a master of theology. Concerns about organizing unsorted data interest him only within the framework of a secular profession. A much more respected theologian is concerned about restoring order in the chaos of modern society, on the eve of the Ascension for true believers and the Last Judgment for everyone else.

As for the algorithm, this is the only sort I know of, for the use of which its inventor requires money.

Scourge

Conservative Baptist, ardent opponent of preterism . The protestant heresy was defeated by Allen 30 years ago in his unfading best-selling book, Ascension Ahead of Great Tribulation (The Pre-Tribulation Rapture, 1980, reprinted in 1999). The result of many years of religious research of our hero is the book “ The Solution of the Ascension - Putting the Puzzle Together ” (“ The Rapture Solution, Putting the Puzzle Together ”).

Benefits

The author really likes to praise his algorithm and he with undisguised pleasure on the sorting site (web-archive) lists its many advantages:

• On average, 2-3 times faster than quick sort , depending on the list.
• Sustainability.
• There are no degenerate cases.
• Does not use comparisons.
• Does not use exchanges.
• Does not use supporting elements.
• It works equally well with short and long lists.
• Economical from memory.
• The first sorted items are already available for use in other processes, while the rest of the list is sorted (in other words, sorting is stable).

In general, all of the above is true. True, instead of comparisons, exchanges and supporting elements, one could say simpler - this is sorting by distribution. Well, about the "economy of memory" can also be debated (but more on that later).

What else is good about sorting - unlike the classic MSD-radix sort, it doesn’t sort by all digits. The process ends immediately as soon as the list is sorted, and not until all digits are processed. You can also specify the number of first ranks by which ordering is performed, if seniority by lower ranks does not have special significance.

Algorithm

Sorting requires two auxiliary arrays.

One of them will be called tracker words (WT - word tracker), by means of it, we will group the words that have the same letters in the i -th digit. For the very first such word found, the value 0 is entered in the list. For each subsequent word found with the same letter in the i- th category, the index of the previous word corresponding to the same attribute is marked in the word tracker.



The table below shows the first sorting step when words are grouped by the first letter. In the process of sorting, when there is a transition from digit to digit, the values ​​in this array change, reflecting a string of words starting with one letter and having the same letters in one place or another.

Another array is the character tracker (LT - letter tracker). It marks the indices of the very first (or last) word in the list, in which the corresponding character is in the corresponding category. Based on this word, with the help of the word tracker, the chain of all other tokens with the corresponding letter in the ith digit is restored .


Now the table shows the indices of the last words from the list that start with one letter or another.

At the given moment, using these two tables, you can pull out all the words, for example, beginning with the letter “B”. To do this, take the cell value LT [1, b] = 9 - this is the index of the last word from the list starting with "b" - Beckie. This word has a track value in the word tracker now: WT [9] = 8 . This is the index of the previous word on "b" - Belinda. The value 6 is stored in the cell WT [8] - Barbara is found under this index, which in turn points to the Beatrix index: WT [6] = 3 . The track value for Beatrix is ​​zero, that is, relative to it, the list does not contain previous words starting with B.

By creating and tracing such strings of words, recursively moving from high-order to low-order, as a result, new sequences are formed very quickly, sorted in alphabetical order. Having sorted the words by “A”, then “B” is sorted, then “C” and then alphabetically.

Time complexity

In general, we can confidently talk about the average time complexity O (k * n) , where k is the number of processed bits.

The company " ASIC DESIGN & MARKETING ", engaged in the development of integrated circuits, implemented the algorithm when creating the PCM ( User Programmable Gate Arrays ). According to the company's engineers, ABCsort is 2.5 to 10 times faster than QuickSort . This can be found in this PDF report .

Memory difficulty

Sorting requires two auxiliary arrays: two-dimensional for the character tracker, which can be neglected when assessing complexity. And also an array of n elements for the word tracker. That is, the overall rating for additional memory is O (n) .

Price

If you liked the algorithm, then take your time to run it in production without paying compensation to the owner. The method is patented ( link to pdf of the patent ) and for its pirated use, the punishing sword of American justice will fall on the thief.

The price for sorting is quite divine, 49 dollars. For this amount, a satisfied customer receives:

• BeechickSort.dll . It contains a sorting function that can be called from any program.
• BeechickSortDemo.exe , as well as sorts to it - BeechickSortDemo.cpp .
• Examples of input data for sorting: SchoolAddresses.txt (records with several fields, you can sort them in different ways) and ShuffledText.txt (a set of random words from the dictionary).
• SortDemo.htm - a web interface for setting sorting options.

If you throw 39 arbitrary units on top, then the DLL will be returned with the commented source in C ++.

Also, an enterprising religious programmer swears by all the saints that if ABC sort is not at least twice as fast as Quick sort , then he will unconditionally return the money.

Algorithm Characteristics

Title	ABC sorting (ABCsort, Allen Beechick Character sort); Beechick sort
Author	Allen Beechick
Year of publication	1993
Class	Distribution Sort
Subclass	Bit Sort
Sustainability	Sustainable
Comparisons	No comparisons
Time complexity	the worst	average	the best
	O (k * n)	O (k * n)	O (n)
Memory difficulty	O (n)

References

Sorting site (web-archive)
Implementation of Lin D. Yarbro in C ++ (web-archive)
Algorithm patent (pdf)
Hardware implementation in integrated microcircuits (pdf)

Allen Beachick

On Facebook
On LinkedIn
The site of the book “The Solution to Ascension - Putting the Puzzle Together”

Voting