SYSTEMS, METHODS, AND DEVICES FOR THE SORTING OF DIGITAL LISTS

This application claims priority to and /or the benefit of U.S. provisional patent application serial number 62 /835 , 326 filed April 1 7, 201 9, U.S. provisional patent application serial number 62 /81 7,022 filed March 1 2 , 201 9, and U.S. provisional patent application serial number 62 /807, 557 filed February 1 9, 201 9. The foregoing applications are incorporated by reference in their entirety as if fully set forth herein.

TECHNICAL FIELD

[0001 ] This invention relates generally to systems, methods, and devices for efficiently and expediently sorting digital l ists. Specific details of certain embodi ments of the invention are set forth in the following description and in the figures to provide a thoroug h u nderstanding of such embodiments. The present invention may have additional embodi ments, may be practiced without one or more of the details descri bed for any particular described embodiment, or may have any detail descri bed for one particular embodiment practiced with any other detail described for another embodi ment.

BACKGROUND ART

[0002] In the field of computer science, a sorting algorith m is an algorithm that is configu red to take a given list, typically in array form, and output a list wherein the elements of the original list are put into a certain order, such as, but not limited to, in numerically ascend ing or descending order for a list comprised of number elements. While simple in descri ption, the problem of efficient sorting is notably complex, and there are numerous different algorithms that represent various approaches to the sorting problem, each with their own strengths and weaknesses. In some computer languages, a“list” is different from an“array” but for the purposes of this application herein the terms refer to a collection of elements which may or may not be equal in value. The elements do not necessarily have to be homogenous, and may, for example, be elements comprised of various numbers of encoding binary bits.

[0003] Among the most fu ndamental tasks in the operation of a computer system is the sorting of l ists, the process of arranging a set of similar pieces of information into a desired order. The vast majority, if not virtually all, database programs employ sorting algorithms, they are also used in other applications including compilers, interpreters, and operating systems. Due to the fundamental importance of sorting algorithms in the operation of computers, making them as efficient as possible improves the performance of computer systems overall.

[0004] When analyzing a sorting algorithm, the amount of computing resources required to execute the algorithm are pivotal to its efficiency. Those skilled in the relevant art will be familiar with what is called“Big O” notation, a means of

mathematically expressing the complexity of an algorithm in terms of factors such as a time complexity and space complexity. In the case of time complexity, algorithms can be further granularly classified base on their worst, best, and average case scenario, with a worst case scenario being particular to a given algorith m such as a list designed specifically to require the most nu mber of operations for that algorith m, while the best case may be a list that is already sorted. Big O notation estimates complexity in an asymptotic sense; estimating the efficiency for a reasonably large length of input.

Generally, for sorting algorithms, the best case scenario, where the list provided is already sorted, would result in O(n). However, most algorithms achieve at best an 0(n log n) ti me complexity for their average and worst-case scenarios.

[0005] A sorting algorithm can be said to have a growth rate on the order of a mathematical function, if, beyond a certain input size n, the function of f(n) times a positive constant provides an upper bound or li mit for the run-time of the sorting algorithm. Put another way, for a given input size n greater than some number and a constant c, the algorith m will run no slower than c*f(n). This concept is what is descri bed by the Big O notation. As an example, if the run-ti me of a given sorting algorithm grows quadratically as its input size increases, the sorting algorithm is descri bed to be 0(n ² ).

[0006] Sorting algorith ms are also categorized by their space complexity, wherein the space complexity increases based on the amount of memory required beyond the amount used by the list being sorted . If, for example, the sorting algorithm created a second copy of the list as it was sorting , the space complexity would double. On the other hand, for lists that swap values as they sort or utilize a“sort in-place” mechanism, the space complexity is equal to, or is so close that the difference is negligible, the size of the original list. The present invention, as an in-place sorting mechanism, utilizes a constant amount of memory.

[0007] Common sorting algorithms known in the art incl ude Quicksort

(someti mes referred to as a partition-exchange sort), mergesort, and Bucket sort.

Frequently they utilize a“divide and conquer” approach by breaking the array into smaller components and sorting them iteratively u ntil the full list is sorted. In the case of Quicksort, a pivot value is selected from the array, and the elements of the array are then moved one-by-one into two sub-arrays, with one su b-array comprised of elements greater than the pivot, and the other comprised of elements less than the pivot. The Quicksort Algorithm then repeats this process recursively, selecting new pivots in the sub-arrays, and essentially swapping the places of elements in the list until they are sorted.

[0008] In the case of mergesort, a given array is broken down into individual elements, wh ich are then compared to their adjacent element to form a sub-list comprised of two sorted elements. The resulting pair lists are then compared to their adjacent pair sub-lists and sorted once more. The algorith m repeats this process with progressively larger su b-lists until the full array is sorted .

[0009] In addition, the present invention resembles Bucket sort, someti mes referred to as a“bin sort.” In a Bucket sort, the algorithm first sets up a n umber of “buckets” in which it will place elements. For example, if the nu mbers are integers ranging from 1 -50, there may be five buckets split into value increments of ten (e.g. 1 - 1 0, 1 1 -20, 20-30, and so on). The algorithm then proceeds through the original array, placing each element it encounters into the appropriate bucket. The algorithm then sorts the buckets si multaneously. Some embodi ments of the algorithm will also check to confirm that a bucket has at least two elements inside it before attempting to sort the bucket, allowing it to potentially ignore empty buckets, or buckets that are comprised of a single element and are thus sorted by definition. Finally, the algorithm moves through each ascending bucket, placing the elements from the lowest value bucket into the array in order, and repeating with ascending value buckets u ntil the final list is produced .

[001 0] The present invention incorporates some aspects of each of the above lists, however it differs i n several key ways, leadi ng to its increased efficiency in terms of time and space, as compared to any individual sorting method.

[001 1 ] Also i mportant to the present disclosure and invention is the method of encoding values in digital lists. Typically, the values in a digital list are encoded using a binary format. In such a format, the number of binary figures used determines the maximum value possible. For example, a binary system that used five bits, where the low-order (rightmost in this case) bit represents a value of 1 , and each val ue doubles beyond that, is capable of representing a maxi mum value of 31 (1 6 + 8 + 4 +2 + 1 ).

The present invention can also be configured to function with alternative encoding mechanisms, depending on the needs of the user.

SUMMARY OF THE I NVENTION

[001 2] The following presents a simplified su mmary of the disclosure in order to provide a basic understanding to the reader. This summary is not an extensive overview of the disclosure and it does not identify key/critical elements of the invention or delineate the scope of the invention. Its sole purpose is to present some concepts disclosed herein in a simplified form as a prelude to the more detailed description that is presented later. [001 3] The present invention exploits the binary encoding of values within a known range of potential values, within a list of a known length, with the result of an O(n) ti me complexity which is dictated by the length of the list multiplied by a constant value, and an 0(1 ) space complexity because the i nvention utilizes a“sort in place” method. The present invention is a non-comparison sort, in that it does not directly compare the values of the individual elements to each other. The system i nvolves examining the binary bits that encode each elements, and as such, the ti me it takes to run the algorith m is dictated by the length of the list to be sorted (N), the maximum number of binary digits used to encode the values (K), and the constant factor based on the computing overhead of the implementation 0)· As written, it would result in a time complexity of O(NKJ); and where N goes to infinity K and J become negligi ble and can drop out, resulting in a time complexity of O(N).

[001 4] The invention considers that when comparing different binary numbers all numbers can be partitioned based on the binary digits. For example, take the list {1 1 1 0, 1 01 1 , 1 1 00, 1 01 0}; all four elements have an active high-order bit, but two of them have an inactive second bit, and two have an active second bit. Due to the nature of binary numbers, it is guaranteed that the value of the two elements with the second bit active will be greater than the value of the two elements with the second bit inactive. Thus the list can be partitioned into two su b-lists comprised of { 1 01 1 , 1 01 0} and { 1 1 1 0, 1 1 00} respectively. Those lists can summarily be partitioned into smaller l ists by looking at the third bit, knowing that, with respect to an element’s current list elements with the same higher order bits, but different third bits, will be comparable in value. So, utilizing the above l ists, the first list { 1 01 1 , 1 01 0} has the third bit active for both values, so no change is made. However, the second list { 1 1 1 0, 1 1 00} has one element with the third bit active and one with it inactive. The system can then further partition that list into another list, resulting in three total lists: { 1 01 1 , 1 01 0}, { 1 1 00}, and { 1 1 1 0}. Fu rthermore, by always moving the highest order bit active elements to the right (or whatever direction the i mplementor has deemed indicates a higher value), and then moving subsequent order bits one step left (or such direction indicates a lower value) of the predecessor bit (as demonstrated in the order of the list in the foregoi ng sentence) it holds true that all lists to the left are comprised of lower value elements than the list on the right.

[001 5] The system can then repeat the process for the lowest order bit, in this case the fourth order bit, and will split the last remaining multi-element l ist in two, creating four lists when it moves the element with the fourth order bit active to the right of its current list but left of the lowest list created by having the second order bit active. The final order is thus: { 1 01 0}, { 1 01 1 }, { 1 1 00}, and { 1 1 1 0}. As is demonstrated , each list is ulti mately reduced to either a single element, or to multiple equal elements, both of which are value sorted lists by definition. Put another way, if the original list had no copies of a nu mber, then no final set would contai n that number; if the original list had one copy of a number, then one final set would contain one copy of that number; if the original list had multiple copies of a number, then one final set would contain all copies of that number. As such, the present invention does not compare the values, but instead relies upon the position of the lists and the bits that encode the lists in order to sort.

[001 6] While the above example utilized integers, there is no restriction on the present invention being utilized with decimal or negative n umbers as well, and a practitioner skilled in the art would easily be able to modify an implementation to do so. The same is true of elements comprised of a variable nu mber of bits with a fixed upper limit. Furthermore, while the above example assu mes a left-to-right ascending order of value, a practitioner could easily adapt the algorith m to operate in the reverse, or such other order as necessary.

[001 7] This invention of systems, methods, and devices for the sorting of digital lists relates generally to algorithmically sorting digital lists, and more specifically the sorting lists of binary-based values. Specific details of certain examples of the system for the sorting of digital lists are set forth in the following description and in the figures to provide a thorough understanding of such examples. The present invention may have additional examples, may be practiced without one or more of the details descri bed for any particular described example, or may have any detail described for one particular example practiced with any other detail described for another example. Many of the attendant features will be more readi ly appreciated as the same becomes better understood by reference to the following detailed description considered in connection with the accompanying drawings.

BRIEF DESCRIPTION OF DRAWINGS

[001 8] The present description will be better understood from the following detailed description read in light of the accompanying drawings, Figures 1 -6, wherein :

[001 9] FIG. 1 is a flowchart for a sorting algorithm according to an embodi ment of the invention ;

[0020] FIGS. 2A-2C shows the sorting process for a sample list of six elements being sorted by the sorti ng algorithm according to an embodiment of the invention ;

[0021 ] FIG. 3 is a flowchart showing the bit counting process of a sorting algorithm according to an embodiment of the invention ;

[0022] FIG. 4 shows a swap-index component that may be implemented with the binary sorting method , in accordance with an embodiment of the invention ;

[0023] FIGS. 5A-5 E show the source code of an example implementation of the invention in the Python scripting language accord ing to an embodiment of the invention ; and

[0024] FIG. 6 is an example of a computing system and network upon which the sorting algorithm may be implemented.

[0025] Like reference numerals are used to designate like parts in the

accompanying drawings. DETAILED DESCRIPTION OF THE PREFERRED EMBODI MENTS

[0026] The detailed description provided below in connection with the appended drawings is intended as a description of the present examples and is not i ntended to represent the only forms in which the present example may be constructed or uti lized. The description sets forth the functions of the example and the sequence of steps for constructing and operating the example. However, the same or equivalent functions and sequences may be accomplished by different examples.

[0027] The examples below describe a new system and method for sorting digital lists. Although the present examples are described and illustrated herein as being implemented in an integer sorting system, the system described is provided as an example and not a li mitation. As those skilled in the art will appreciate, the present examples are suitable for appl ication in a variety of different types of sorting systems.

[0028] FIG. 1 is a block diagram showing a basic flow of the algorithm 1 00 as it sorts an array. First step 1 02 , the algorithm sets a Pointer to examine the n-th bit of a binary encoded element of a list. For example, for elements encoded in four bits, it would examine the fourth and highest order bit. The algorithm then proceeds through the array for step 1 04, moving the pointer to exami ne the highest order bit until it encounters a bit that is active (typically denoted as a bit set to 1 instead of 0). When it encounters that active bit for step 1 06, it creates a sub-list and moves the element with the active bit to the end of that sub-list as step 1 08. In some embodi ments, it may be preferable to more the element to the beginning of a sub-list, or to an x- 1 position wherein x is the position of the last element moved to the sub-list. This sub-list creation process can alternatively happen at the beg inning of the algorithm, or can be postponed until the active bit is found.

[0029] The algorithm then proceeds sequentially through the original list, moving each element it encounters with the current examined bit active to the current sub-list as step 1 1 0. Once it reaches the end of the process, there should be an original list and the sub-list, the latter containing the entirety of the elements with the bit the Pointer was designated to check set to active.

[0030] The algorithm then reduces the order of bit the Poi nter is examining by one, step 1 1 2 , so in the case of a four order encod ing, the Pointer would now be set to the third bit. Then algorithm then repeats the original process; examining each element on the original list and any existing sub-lists in order (or in some embodi ments multiple copies of the algorith m can run pointers on each l ist simu ltaneously), and moving any encountered elements to a new sub-l ist. However, when it is examining a sub-list, instead of moving elements encountered to the sub-list the algorithm created for the original list, it instead creates an additional sub-l ist for elements that came from each existing su b-list. So, for example, if the first pass of the algorithm created a sub-list with two elements, and one of those elements had the third order bit set to active, that element wou ld be moved from the first sub-list to a new one, set between the originally created sub-list and the original list.

[0031 ] Finally, the algorithm terminates when the Pointer value is set to zero at step 1 1 4, meaning it has examined each order of bits attached to the elements. At this time, the original list should be empty and the algorithm can combine all of the sub lists into a sorted list.

[0032] In some embodiments of the algorithm the system can add a further

“cou nting” sort method to the beginning of the algorithm in order to streamline the process. If sorting a list into two distinct sets of values, one set all greater than the other, then one can further sort those two subsets based on a next lower set of contiguous bits, confident that the same property will apply for those sets. As one further sorts based on progressively lower sets of significant digits, the original list becomes more and more sorted . When all sub-lists have been sorted, meaning the original list has been reduced to a single or multiple equal elements, on the lowest set of significant bits then the entire list has been properly sorted. The i mplication of this is that no matter what the value of N is for a list of length N, the number of times that N items are processed is a function of the number of bits in the encoding of the individual numbers, and the length of the list. Assuming K bits, then the ti me complexity of this process is O(NK). In modern computing, all items in a list use the same n umber of bits for encoding, thus K, for practical purposes, is a constant for any particular list. Thus the K drops out of the time complexity as being negligible as N approaches infinity, and it leaves O(N).

[0033] This counting addition can thus create“buckets” of a size relative to how many times each bit configuration appears in the l ist. Knowing the start of the next set (or“bucket”) in a list also lets the algorithm potentially know the end of the previous bucket. If one adds in an“extra” pointer at the end of each bucket and has it advance backwards, one can sort based on one more bit lower down than one had counted with. This would be similar to sorting on the first bit of a set of items when the algorithm only knows the length of the l ist. One pointer starts on the left, another on the right, and they advance and trade items until they meet, similar to Quick Sort.

[0034] When each bucket has been filled with elements corresponding to the bit config uration it represents, then the next level of sorting could be kicked off then, instead of waiting for the whole sub-list to be sorted. This would result in loss of the ability to consistently sort to the smallest or largest values first, but would speed up when the in itial set of final locations for some val ues wou ld be known. This

config uration may have merit for gambling or display purposes. A random or semi random list sorted in this manner could be used as a contest to place wagers on as to what n umber or numbers will be in the first or su bsequent sets of nu mbers to be finished sorting. In entertainment media it is not uncommon for an empty or unknown list to be slowly sorted with seemingly random val ues along the list becoming visible in a nonlinear fashion. This configuration of the algorithm could provide such an effect.

[0035] In addition, this algorithm can be executed linearly or recursively, with the typical tradeoffs in use of computing resources and ti me efficiency that accompany each choice. [0036] FIGS. 2A-C (collectively FIG. 2) is an example of the algorith m 1 00 in process through a simplified sample array of whole integers. The algorithm 1 00 begins with an u nsorted list 200 of elements 202 , 204, 206, 208, 21 0, 2 1 2 which in this case is comprised of the elements 2 , 1 , 5 , 22 , 31 , and 8 encoded into five orders of bits with the rightmost bit being the high order and the leftmost being the low-order bit such that a number with each bit active would be 31 , and a number with each bit inactive would be 0, and the bits, in order from left to right, represent the values of 1 6, 8, 4, 2 , and 1 respectively. In the present invention, a pointer begins moving from left to right, though the direction is provided solely for interpretive purposes and is not a restriction of the system, and looks for an element with the hig h-order bit set active. In the present example, it first encounters the element corresponding to the val ue 22 , element 208, wherein the high-order bit is active as demonstrated in step 21 4. The algorith m 1 00 then creates a su b-list 21 6 and moves the element representing 22 to its end. The algorithm 1 00 then proceeds through the original list again, encountering the element with the value 31 , element 2 1 0, which also has a highest-order bit active (as the pointer is tracking the highest order bit), and as shown in step 21 5 , moves it to the beginning of sub-list 2 1 6.

[0037] Now the process repeats for the next step 21 7 by spawning a second copy of the algorithm for the sub-list and running itself on the original unsorted list 200. The algorithm 1 00 reduces the bit order the pointer is inspecting by one, so it is looking for an active bit one order bit lower than the hig h-order bit, in this case the bit representing a value of 8. The algorithm 1 00 begins looking at both the original unsorted list 200 and the sub-list 21 6. The algorith m encounters the element with the value 8, element 2 1 2 , and the element with the value 31 , element 21 0, as each has an active second highest order bit. The 31 element 21 0 is moved to a new sub-list 21 8 to the right of the first spawned sub-list 2 1 6 as shown in step 2 1 9, while the 8 element

21 2 is moved to a new sub-list 220 left of the first sub-list. [0038] The process repeats on the original unsorted list 200 and all the created sub-lists 2 1 6, 21 8 and 220, creating new copies of the algorithm for each list, and reducing the order of bit it is examining by one, so that it now examines the third bit in the series. In the unsorted original list, the pointer encounters the element with the value 5 , element 206, which has an active third bit as shown in step 22 1 . Like in the prior iterations, it moves to the value 5 element 206, to a new sub-list 222 positioned left of all previous sub-l ists 2 1 6, 21 8, and 220, but right of the unsorted original list 200 as demonstrated in step 223. The spawned versions of the algorithms also encounter activated bits in the su b-lists 2 1 6 and 21 8 for the 22 and 31 elements, 208 and 21 0 respectively, but as those lists are l ists comprised of one element, zero elements, or equal elements, the algorithm knows that they are by definition sorted and does not need to move them. In some embodi ments, the algorithm may check a list of equal value elements, wh ile in others it can be configured to remember when lists of equal value elements have been created.

[0039] The process of moving the 5 element 206 to the sub-list 222 also creates a new instance of the algorithm to potentially run on that sub-list; while in some embodi ments it may be configured to notice that it has created a single element list by the end of its runti me and may terminate due to a single element list being sorted by definition.

[0040] For the fourth iteration, the algorith m reviews the fourth highest order element, the bit corresponding to a value of 2 , and immediately encounters the element with the value 2 , element 202. As before, the algorithm creates a new sub-list 224 and moves the 2 element 202 to that sub-list 224 as indicated in steps 225 and 226. For the other instances of the algorithm running on other lists, they also encounter the 22 element 208 and 31 elements 21 0, but as before, do not operate on them because they are by definition sorted. With the 2 element 202 moved, all six elements now occupy six single-element lists 200, 2 1 6, 21 8, 220, 222 , and 224 as shown in step 226. By definition each of these single element lists is sorted, so the algorithm can recombine them, in their current order, into a single array 227 that is also sorted as shown in step 228.

[0041 ] In order to sort a list usi ng the algorith m, the l ist to be sorted needs to be in the form of an array, and in some embodi ments the length of the array must be known in advance. The items in the array need to be logically encoded in a standard binary format consistent across the values in the l ist without interdependence between values.

[0042] The algorithm sorts the list by using“levels” of contiguous bits from most significant to least significant for the individual items in the array. While there is no requirement that the same number of bits be used in each level, that practice will be assu med in order to si mplify the examples herein. In some embodiments, the elements may not all utilize every single bit, and a practitioner skilled in the art could readily adjust an i mplementation to compensate for such loss by initially having the algorith m treat elements without certain levels of bits as having inactive bits. In some examples, multiple bits may be examined at the same time. Using the example from before, if the elements are {001 1 } and {01 00} the algorithm could instead partially exami ne the first two bits, the 00 and 01 respectively, and sort accordingly such that a“1 1” bit pair is treated as the highest value and placed on the rightmost (for simplicity, higher values are being placed on the right) list, the“1 0” on the next highest, the“01” on the third highest, and the“00” on the lowest value sub-list.

[0043] Each level of sorting assumes the value of the item is temporarily the equivalent value of the set of bits being sorted on . For example, if sorting on 2 bits at a time a set of 4-bit numbers, and there was a need to sort 3 (represented as {001 1 }) and 4 (represented as {01 00}) by their 2 most significant bits, then one would be sorting them with the respective values of 0 from the“00” component of (001 1 ) and 1 from the “01” component of (01 00) as derived from the active bits examined in the first, or highest order, pair. [0044] As stated previously the algorithm uses the fact that all numbers whose one set of most significant bits is greater than the set of most significant bits of other numbers are also of greater total individual value of all individual values of the other numbers. This is irrespective of the value of the lower sets of bits. Thus 1 2 { 1 1 00} is greater than all numbers one less in the 2 ^nd most significant digit: 1 1 { 1 01 1 }, 1 0 { 1 01 0}, 9 { 1 001 }, and 8 itself { 1 000}. The algorithm can rely on this fact to ensure that active higher order bits result i n the sub-lists created containing elements with those active higher order bits are higher than those without the active higher order bits.

[0045] The process of subdividing can be advanced by noting that, for a given set of bits, there is a sorted order for each pattern of bits. Such as the values 00, 01 ,

1 0, and 1 1 will be sorted ascending in that order no matter where in the process they are found. Thus, if one knows where in the sub-list the full set of nu mbers with each of those patterns should reside, one can sort to those nu mbers into those locations without regard to any ordering within the numbers having the same pattern at the level being sorted. As a result all numbers with 00 will be before all nu mbers with 01 , and so on .

[0046] FIG. 3 is a flowchart showing the bit counting process of a sorting algorithm according to an embodiment of the invention.

[0047] In some i mplementations of the algorith m, counting the number of elements in a list containing the same pattern of bits in the same location in each value enables one to improve the ability to move values closer and closer to their final location in the sorted final list. This technique has an advantage whereby the sorti ng is done by copying values within the original array. However, it is also possible to dispense with copying values partially or entirely in order to generate a sorted copy of the original list.

[0048] The basics of a counting sort 300 is to count the nu mber of instances of each number in a list. These counts may be kept i n another list, such as an array the size of the maxi mum range of the numbers being sorted as shown in step 302. In cases where the numbers being sorted are attached or associated with other data, it is can be useful to keep the original ordering when the final sorted list is created. If there are th ree elements with the value " 1 2", then the order they appear in the origi nal list when apart or together may need to be maintained when they appear together i n the sorted list. Additionally, the original values along with their attachment to additional data would generally need to be copied to their new locations. If a particular implementation does not require the order of the elements be preserved, then the sorting can be simplified.

[0049] In simplified terms, the count sort B00 proceeds by creating a count array with a nu mber of elements equal to the number of possible bit configurations; the square of the number of bits being examined, as shown in step B02. The sort then utilizes a pointer or si milar tracking mechanism to proceed sequentially through the array, examining the highest order bit(s) as configured as shown in step 304, and increasing the element i n the count array by one each time the count array element’s corresponding bit configuration is encountered in the source array as shown in step 306. The process repeats through the entire array, step 308, and as output can provide the system or a user with the count array, step 31 0.

[0050] If one were to know how many copies of each individ ual nu mber exist in a list, in a sorted order, then it would be si mple to build a new list from that

information. The problem with this approach until now is that the "counti ng" list could easily be larger than the original list. What the counting component of the algorith m does is count based on portions of the values, with a bias towards completing the count of the smaller (or larger) numbers earlier in the process. Thus, the full count of the numbers are completed first, and can be written out to an output list (of the same size as the original) before moving on to the greater numbers. Since the previous numbers have been fully dealt with, the space used to count those numbers can be reused to finish cou nting the next larger numbers.

[0051 ] When operating at each level the algorithm is given a few key pieces of information : the pattern of bits "above" the pattern to be used for counting, the nu mber of instances of that "above" pattern to be found, the location of the original array being sorted, and for the lowest level instance the location of the output array. In addition, because the counts are known, it is possible to also pass the starting index of a grou ping of values, such that the algorith m can be ru n in parallel.

[0052] The count sort component can be i mplemented i ndependently, or as a supporting function of the existing binary examination sorting.

[0053] For a non-optimized example, the count sort could operate as follows.

Take four 8-bit values, d ividing the values into 2-bit seg ments for the purposes of counting. An input array of 4 positive values {255 , 1 32 , 1 8, 255 }. In binary form, the arrays appears as { 1 1 1 1 1 1 1 1 , 1 00001 00, 0001 001 0, 1 1 1 1 1 1 1 1 }. Create an output array of the same size of the i nput array {0, 0, 0, 0}.

[0054] For each pass at a particular level , create a counting array of a number of elements equal to 2 to the power of the nu mber of bits in that pass. In this case the number of bits will always be 2 , so the counting arrays will always have a length of 2 to the power 2 , which equals 4, so the counting array will start as {0, 0 ,0, 0}.

[0055] Because this is the first pass, the number of elements to be counted is equal to the length of the original array to be sorted. The pattern of bits "above" the patterns being counted in this iteration are effectively blank, and su perfluous for the first iteration. The algorithm will work with 2 bits at a time at 4 levels. For counting purposes, the algorith m only needs to "see" the relevant set of (2) bits from within the value. Thus, the input array values would be counted by the first 2 bits, and the number of instances is put into the appropriate indices of the counting array being used for that level . The 2-bit values from the input array would appear as { 1 1 , 1 0, 00, 1 1 }, which in digital form would be {3, 2 , 0, 3}. The underlining below wi ll show the values as they are processed by the algorithm:

Input: {11, 1 0, 00, 1 1 }— Counting : {0, 0, 0, 1 }

Input: { 1 1 , J_0, 00, 1 1 }— Counting : {0, 0, 1 , 1 } Input: { 1 1 , 1 0, 00, 1 1 }— Counting : { 1 , 0, 1 , 1 }

Input: { 1 1 , 1 0, 00, JJ — Counting : { 1 , 0, 1 , 2}

[0056] Please note that the index for each element in the counting array matches the binary value of the bit pattern being counted at that index.

[0057] In some embodiments, once the original list has had its elements counted into the counting array, the algorith m goes through the counting array and writes any single value count into the output array calls another instance of the algorithm for each element that has a value greater than 0. This allows it to count and potentially sort lower orders of bits.

[0058] FIG. 4 shows a swap-index component that may be implemented with the binary sorting method , in accordance with an embodiment of the invention.

[0059] When implemented with a swap-index system 400, the counting method can also function as a sorting means. First, the system goes through the counting sort algorithm as in step 402 , described in FIG. 3, resulting in an array with a number of elements equal to the nu mber of possi ble bit configurations of the number of bits being examined, which is also the square of the number of bits being examined . For example, if the system 400 is examining two bits, then the possible configurations are 00, 01 , 1 0, and 1 1 , resulting in four swap-indexes and four bucket sub-lists. In some

embodi ments, the system may be configured to not create a swap-index for any config uration whose count was zero.

[0060] In such cases, the system may create a“swap-index” for each possible config urations of bits being examined in step 402 , as shown in step 404. The swap- indexes begin at an element a number of places in equal to the total number of elements in the preceding buckets. For example, if the possible configurations are 00, 01 , 1 0, and 1 1 , and there are three elements with a 00, four with a 01 , one with a 1 0, and two with a 1 1 config uration, then the swap-index for the 1 1 configuration will start at the 9 ^th place in the array, the swap-index for the 00 config uration will start at the 0 ^th place in the array, the 01 swap-index will start at the 4 ^th position in the array, and the 1 0 swap-index will start at the 8 ^th position in the array as shown in step 406. The swap-indices can further be configured to only proceed until they reach the known end of their bucket sub-array, which would be one less than the starting position of the swap-index that follows them. So in the preceding example, the 00 swap i ndex would be configured to end at the 3 ^rd position in the array.

[0061 ] Each swap-index will then advance one at a ti me from left to right as shown in step 408. Then the system will also create a number of“bucket” sub-lists equal to the number of possible configurations of bits being examined and associated with the corresponding swap-index for each configuration, with each bucket sub-list starting at the same position as its associated swap-index.

[0062] The advancement will temporarily stop when the swap-index is at an element that does not belong in that bucket as shown in step 41 0. Once all active swap- index values have advanced to either an element that does not belong, or past the end of the bucket, then the moving of elements will commence. Please note this i mportant feature: the bit(s) used to count in the previous iteration, and now to sort in this iteration, when taken independently of the original value from whence they came, represent a numeric value that matches the bucket to which the value they reside in need to be sorted. In the case of a 2-bit counting mechanism, it would be a 2-bit numeric value.

[0063] Once all swap-indices have“stopped,” or reached a value different from the bit configuration each is looking for, the values will be sequentially moved to the current location of thei r "home" bucket's swap-index, or the bucket that is associated with a bit configuration that matches the bit configuration of the element as descri bed in step 41 2. In the case where two buckets' swap-indices are on values belonging in the other, then a si mple swap can occur and both swap-indices can be advanced to the next unwelcome value or past the end of their section. In the case where multiple swap- indices are on values belonging to the same other bucket, then the values can be swapped in intelligently, one at time, advancing the receiving swap-index properly after each, potentially using a temporary holding variable for any "orphan" values that do not cu rrently have a spot clear for them to go into.

[0064] The exact details of the swapping procedure are subject to opti mization for the specific circumstances of the execution of the algorith m. These details are easily decided by a person knowledgeable in the field of computer science. One of the primary advantages of this technique is that the compared part of the value also exactly identifies the bucket in which it must arrive. There is no need to create or associate a separate value to represent that bucket to the original value to be sorted. I n some embodi ments, the algorithm can then proceed with the original binary encoding sort algorithm described above, treating each bucket as a source array as shown in step 41 4. Alternatively, the swap-index system can repeat, examining lower-order configurations of bits within each bucket.

[0065] Example and Explanation of Python Implementation and Sorting Method

[0066] FIGS. 5A-E, (collectively FIG. 5) comprise source code for an

implementation of a binary encoding bit sorting algorithm combined with the add itional counting featu re, in accordance with an embodiment of the invention. The included code is provided only as an example i mplementation, not an exhaustive version. For the purpose of the example, several variables and functions have been defined , as discussed below.

[0067] The currentPointer is a si ngle value holding the ordinal of the pointer cu rrently being worked with.

[0068] The Pointers array is a one-dimensional array of size equal to the maximum value represented by the number of bits being sorted on, holding the current locations into the list bei ng sorted for each pointer. As a note, for convenience purposes for this example, the value for each poi nter in this array will be the current index of the pointer, save for the case where the pointer has gone past the end of its own bucket. In that case the value will be set to - 1 as an indicator that this pointer is no longer in use for sorti ng for this iteration . Note that currentPointer is used as an index into the Pointers (as well as Next and Prev below) array. The value in

Pointers[currentPointer] is the index into the original list being sorted at which cu rrentPointer is pointing.

[0069] The oldCounts array is the same size as the Pointers array, and holds the counts for the set of bits being sorted on at this level, and this information is used to summatically both initialize the Pointers array and create the Ends array. A summation value is created that equals the first of the oldCou nts ([0]) fields plus the beginning index of the (sub)list bei ng sorted. For the first level, the beginning index is 0. The first value of the Pointers array ([0]) is set to this value. The summation value has added to it the first field of the oldCounts array, and then the first field of the Ends array is set to that value. Repeat until all values in Pointers and Ends have been set. The result is Pointers starting at a 0 offset from the beginning of the section of the orig inal list that is being sorted, and Ends has as its last value one past the index of the last value of the original list that is being sorted. In between, the summation count fills both arrays, with the value at any particular index (after 0) of Pointers having the same value as at that index minus one of Ends.

[0070] The Next, and Prev arrays are each the same size as the Pointers array, and are necessary for resolving trading values between pointers. For convenience purposes, the default val ue of the elements of these arrays is - 1 , which indicates the value for that particular pointer is not set.

[0071 ] The newCou nts is a two-dimensional array with the first dimension equal the size of the Pointers array, and the second dimension equal to a size eq ual to the maximum value represented by the number of bits bei ng counted on. For this example, the nu mber of bits counted on will consistently match the number of bits being sorted on , but that is not a required choice in the general case of sorting a list.

[0072] arrList is the one-dimensional list of values to be sorted. [0073] IntraValue is the term coined to refer to the value of a contiguous set of bits from within the full set of bits used to represent a value in the list to be sorted. These bits are treated as if they were the only bits in a value, for example, 01 1 000 using the midd le pair of bits an IntraValue of (binary) 1 0, deci mal (4) would be obtained.

[0074] Upperlntra value will refer to the set of bits being sorted on.

[0075] Lowerlntra value will represent the next lower distinct set of bits

(adjacent to those used for IntraValue) being cou nted on.

[0076] numBits is the nu mber of bits used for sorting and counting in this example. For this example its value is always 2.

[0077] Isb is a value representing the number of bits remaining below the level being sorted’s Upperlntra value bits. The Upperl ntra value is evaluated at the bits starting (from the left ) one greater than Isb. To begin with, Isb in this example will be 4. Similarly, Lowerlntra value is evaluated at the next numBits below where Upperlntra value is evaluated . This is to accommodate using a mask and bit shift operations to obtain IntraValues, but that is an implementation detail that is not strictly necessary in order to understand the algorithm. What is key, though, is that by lowering the value of Isb by numBits for subsequent levels of sorting Isb eventually becomes eq ual to 0 for particular iterations of the algorith m, and that is an indicator that only sorting of the last bits of the values is necessary and trying to count below those bits is pointless.

[0078] Exemplary Computing device

[0079] FIG. 6 is an example of a computing system upon which the new sorting algorithm may be implemented. Exemplary computing environ ment 600 is only one example of a computing system and is not intended to li mit the examples descri bed in th is application to this particular computing environment.

[0080] For example the computi ng environment 600 can be i mplemented with numerous other general purpose or special purpose computing system configu rations. Examples of well known computing systems, may include, but are not l imited to, personal computers, hand-held or laptop devices, tablets, microprocessor-based systems, multiprocessor systems, cellular telephones, PDAs, and the like.

[0081 ] The computer 600 includes a general-purpose computing system in the form of a computing device 601 . The components of computing device 601 can include one or more processors (including CPUs, GPUs, microprocessors and the like) 607, a system memory 609, and a system bus 608 that couples the various system

components. Processor 607 processes various computer executable instructions, including those to implement the algorithm and to control the operation of computing device 601 and to communicate with other electronic and computing devices (not shown). The system bus 608 represents any number of several types of bus structures, including a memory bus or memory controller, a peri pheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures.

[0082] The invention algorithm may, in some embodi ments, utilize a "look ahead" mechanism to compare and count patterns of bits, and then uses those same patterns to route values to the correct subsets for the pertinent level of sorting.

[0083] Since the number of bits used in a standard computer system is known at time of manufacture, and is permanent for the life of the processors used in the computer, it is possible to do hardware level opti mization specifically, al beit not necessari ly exclusively, for the algorith m.

[0084] Normally, a contiguous subset of the bits used in a value are evaluated as if they were an independent number in and of themselves. When such a grouping of bits is retrieved from a value, when they are not the last and least significant bits of that value, they have to be "translated" into the equivalent of the number they would represent independently of the value from which they were extracted . By creating special instructions in the gate-logic of a computing device 601 , it is possible to bypass the "translation" step. Such could also be implemented into the construction of the processor’s 607 register, wherein the specific gates could be part of its memory. [0085] Normally, any kind of copy operation is done on a whole value with each bit being faithfully copied to the same relative location within the bits of the copied-to location. By specifically copying a contiguous subset of bits to the lowest values in the copied-to location, the new value at the copied to location will be the desired value already.

[0086] For example, given a value of " 1 1 01 1 ", the integer "25", and an embodi ment of the algorithm consistently using 2 -bits for counting, would be a need for (from left to right, starting with 0) bits 1 and 2 (" 1 0") and for bits 3 and 4 (" 1 1”).

[0087] Dedicated logic-gates implemented in the computing device 601 would have an instruction to copy bits 1 and 2 to a new value. Another instruction would copy bits 3 and 4 to a new val ue. These instructions wou ld be independent, and at a low level implemented as part of the instruction set of the computing device 601 .

[0088] The exact ordering of the bits would be up to a designer of the relevant ch ip. A practitioner skilled in the art could instead structure a chip with the bits out of order, or in a different order, and the present invention could be adapted thereto. In other words, the algorith m could be adapted to any binary architecture.

[0089] The system memory 609 includes computer-readable media in the form of volatile memory, such as random access memory (RAM), and /or non-volatile memory, such as read only memory (ROM). A basic input/output system (BIOS) is stored in ROM. RAM typically contains data and /or program modules that are immediately accessible to and /or presently operated on by one or more of the processors 607.

[0090] Mass storage devices 604 may be coupled to the computing device 601 or incorporated into the computing device by coupling to the bus. Such mass storage devices 604 may include a magnetic disk drive which reads from and writes to a removable, non-volatile magnetic disk (e.g ., a“floppy d isk”) 605 , or an optical disk drive that reads from and /or writes to a removable, non-volatile optical disk such as a CD- ROM or the like 606. Computer readable media 605 , 606 typically embody computer readable instructions, data structures, program modu les and the like suppl ied on floppy disks, CDs, portable memory sticks and the like.

[0091 ] Any number of program modules can be stored on the hard disk 61 0,

Mass storage devices 604, ROM and /or RAM 609, including by way of example, an operating system, one or more application programs, other program modu les, and program data. Each of such operating system, application programs, other program modules and program data (or some combination thereof) may include an embodi ment of the systems and methods described herein.

[0092] A display device 602 can be connected to the system bus 608 via an interface, such as a video adapter 61 1 . A user can interface with computing device via any number of different input devices 603 such as a keyboard , pointing device, joystick, game pad, serial port, and /or the like. These and other in put devices are connected to the processors 607 via in put/output interfaces 61 2 that are cou pled to the system bus 608, but may be connected by other interface and bus structures, such as a parallel port, game port, and /or a universal serial bus (USB).

[0093] Computing device 600 can operate in a networked environment using connections to one or more remote computers th rough one or more local area networks (LANs), wide area networks (WANs) and the like. The computing device 601 is connected to a network 61 4 via a network adapter 61 3 or alternatively by a modem,

DSL, ISDN interface or the like.

[0094] The functionalities described herein are not envisioned to be tied to any one communication protocol, programming language or the like, and may be implemented in any convenient form of coding, computer language or the like where called for to implement a particular function in the algorithm.

[0095] Those skilled in the art will realize that the process sequences descri bed above may be equivalently performed in any order to achieve a desired result. Also, sub-processes may typically be omitted as desired without taking away from the overall functionality of the processes described above. [0096] While the above example of a computing environment is one possible implementation , those skilled in the art could also attempt to implement the present invention in nearly any environment capable of i mplementing a computer, such as in a suitably programmed video game or utilizing a mechan ical implementation. For example, practitioners have created virtual“computers” in popular sandbox video games such as Minecraft, and, g iven the proper tools, could i mplement this invention in such a game, or in other med ia.

[0097] Those skilled in the art will realize that storage devices utilized to store program instructions can be distributed across a network. For example a remote computer may store an example of the process described as software. A local or terminal computer may access the remote computer and download a part or all of the software to run the program. Alternatively the local computer may download pieces of the software as needed, or distri butively process by executing some software instructions at the local terminal and some at the remote computer (or computer network). Those skilled in the art will also realize that by utilizing conventional techniques known to those skilled in the art that all, or a portion of the software instructions may be carried out by a dedicated circuit, such as a DSP, programmable logic array, or the like.