This type of bitwise MSD sort is “sharpened” for strings. However, the algorithm is so named not for lexical specialization. Author Allen Bichik (Allen Beechick) chose a name in honor of himself, ABCsort stands for Allen Beechick Character sort .

Bychik himself is remarkable in that he is not only a programmer, but also a master of theology. The concern of streamlining unsorted data interests him only within the secular profession. Much more respected theologian is concerned with restoring order in the chaos of modern society, on the eve of Ascension for true believers and the Last Judgment for all others.

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

')

Bichik

A conservative Baptist, an ardent opponent of preterism . The Protestant heresy was crushed by Allen 30 years ago in his unfading best-selling book “The Ascension on the Eve of the Great Tribulation ” (“The Pre-Tribulation Rapture”, 1980, reprint in 1999). The result of our hero's perennial religious research is the book “ The Ascension Solution - Putting the Puzzle Together ” (“ The Rapture Solution, Putting the Puzzle Together ”).

Benefits

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

• On average, 2-3 times faster than quick sorting , depending on the list.
• Sustainability.
• No degenerate cases.
• Does not use comparison.
• Does not use exchanges.
• Does not use support elements.
• 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, the sorting is stable).

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

What else is good sorting - in contrast to the classic MSD-radix, sort does not sort by all digits. The process stops as soon as the list is sorted, and not until all digits are processed. You can also specify the number of first digits by which ordering will be performed, if seniority by lower digits does not have special significance.

Algorithm

Sorting requires two auxiliary arrays.

One of them is called the word tracker (WT - word tracker), with the help of it we will group 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 found word with the same letter in the i- th digit in the word tracker, the index of the previous word corresponding to the same sign is noted.



The following table shows the first stage of sorting, when words are grouped by the first letter. In the process of sorting, when the transition from discharge to discharge occurs, the values ​​in this array change, reflecting chains of words starting with one letter and having the same letters in one place or another.

Another array is a symbol tracker (LT - letter tracker). It marks the indices of the very first (or last) word in the list, in which a certain character is in the corresponding digit. Starting from this word, with the help of the word tracker, the chain of all other lexemes that have the corresponding letter in the i- th digit is restored.


Now the table shows the indices of the last words from the list, which begin with one or another letter.

At this point, using these two tables, you can pull out all the words, for example, starting with the letter “B”. To do this, take the value of the cell LT [1, b] = 9 - this is the index of the last word from the list beginning with “b” - Beckie. This word in the word tracker has a track value 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] - under this index is found Barbara, which in turn indicates the index Beatrix: WT [6] = 3 . The track value for Beatrix is ​​zero, that is, there are no previous words starting with B in the list.

Creating and tracing such chains of words, moving recursively from higher digits to younger ones, as a result, very quickly new sequences are formed, arranged in alphabetical order. Sorting the words into “A”, then “B” is sorted, then “C” and then alphabetically.

Time complexity

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

The company ASIC DESIGN & MARKETING , which is engaged in the development of integrated circuits, implemented the algorithm when creating an FPGA ( User-programmable gate arrays ). According to the company's engineers, ABCsort works 2.5 to 10 times faster than QuickSort . You can read about this in this PDF report .

Memory difficulty

Two auxiliary arrays will be required for sorting: two-dimensional for the character tracker, which can be neglected when estimating complexity. As well as an array of n elements for the word tracker. That is, the total estimate of additional memory: O (n) .

Price

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

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

• BeechickSort.dll . This contains a sorting function that can be called from any program.
• BeechickSortDemo.exe , as well as its links to it - BeechickSortDemo.cpp .
• Examples of source data for sorting: SchoolAddresses.txt (entries with several fields, you can sort them differently) and ShuffledText.txt (a set of random words from the dictionary).
• SortDemo.htm - web interface for setting sorting parameters.

If to throw over 39 conventional units, then DLL-ku will be given with commented source codes in C ++.

An enterprising religious scholar and programmer swears by all the saints that if ABC sort does not turn out to be 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	Sort by distribution
Subclass	Bitwise sorting
Resilience	Steady
Comparisons	No comparisons
Time complexity	the worst	average	the best
	O (k * n)	O (k * n)	O (n)
Memory difficulty	O (n)

Links

Sorting site (web archive)
Lina D. Yarbrough implementation in C ++ (web-archive)
Algorithm Patent (pdf)
Hardware implementation in integrated circuits (pdf)

Allen Beachick

On Facebook
On LinkedIn
The site of the book “The solution of Ascension - let's put the puzzle together”

Voting