Patent ID: 7509309

Claim:
A method, comprising executing an algorithm by a processor of a computer system, said executing said algorithm comprising sorting S sequences of binary bits in ascending or descending order of a value associated with each sequence and in a time period denoted as a sorting execution time, said S sequences being stored in a memory device of the computer system prior to said sorting, S being at least 2, each sequence of the S sequences comprising N bits, N being at least 2, said sorting comprising executing program code at nodes of a linked execution structure, said executing program code being performed in a sequential order with respect to said nodes, said executing program code including: specifying a constant mask width W which defines a mask of width W and further defines L contiguous fields in each sequence and L levels denoted as Level 1, Level 2, . . . , Level L, wherein the L contiguous fields of each sequence are denoted as F 1 , F 2 , . . . , F L , wherein N is an integral multiple of W, wherein L =N/W such that L is at least 2, wherein the linked execution structure comprises a Level 0 and the L levels, and wherein Level 0 is a root node comprising the S sequences; masking field F i+1 in Level i+1 to define 2 W child nodes in Level i+1 for each node in Level i such that each node in Level i is a parent node of its 2 W child nodes in Level i+1 (i =1, 2, . . . , L−1), wherein each child node of the 2 W child nodes in Level i +1 for each parent node in Level i is associated with a unique value of field F i+1 (i =0, 1, . . . , L−1); recursively traversing a sufficient number of paths through the linked execution structure to complete said sorting S sequences, wherein each path traversed comprises an ordered sequence of nodes passing through one and only one node in each level of Level 1, Level 2, . . . , Level T such that 1≦T≦L, wherein said recursively traversing comprises distributing into each node of Level i+1 all sequences in its parent node in Level i which match the unique value for field F i+1 for each node in Level i+1, wherein each node in each path includes at least one sequence of the S sequences, wherein for each path the node in Level T is a leaf node that terminates each path, and wherein for each path either f=L or T<L due to the node in Level T having one and only one sequence therein: and outputting each sequence of the S sequences or a pointer thereto to an output array of the memory device whenever said recursively traversing terminates each path at its leaf node in Level T.