Patent ID: 7236495

Claim:
A method for sorting N timestamp (TS) values in an Asynchronous Transfer Mode (ATM) fabric scheduler implemented in an access network element, comprising the steps: selecting a radix (R) value for grouping said TS values into N/R groups, wherein each group is associated with a set of bits corresponding in number to said radix value, said bits for indicating which of said group's TS values are valid; creating a plurality of layers in a hierarchical tree arrangement wherein said set of bits forms a layer of log R (N) level and each layer includes a group of heap structures equal in number to R [Level-1] , Level=1,2, . . . , log R (N), and further wherein each heap structure includes R number of bits and R number of pointers, said pointers of a Level(i) layer pointing to heap structures of Level(i+1) layer, where i=1,2, . . . , {log R (N)−1}; and starting from a Level-1 heap structure, successively determining via a Least Significant Bit (LSB) finder operating on said R number of bits for a particular heap structure on Level(i) layer which heap structure on a particular subsequent Level has a minimum value until said log R (N) Level is reached.