Patent ID: 8463820

Claim:
A computer implemented method, comprising: providing a plurality of lists of data, wherein each list is stored in a corresponding leaf node of a plurality of leaf nodes, the plurality of leaf nodes residing in memory storage coupled to the platform; building a d-ary tree of a plurality of cache resident nodes from the plurality of lists of data, wherein the plurality of cache resident nodes are resident in a cache memory and are sized such that all of the cache resident nodes can reside in the cache memory simultaneously, the building comprising: merging a block of data elements from each leaf node into a first set of parent nodes, the first set of parent nodes being immediate parents of the leaf nodes and being cache resident nodes, merging blocks of data elements from the first set of parent nodes to a next set of parent nodes, the next set of parent nodes being cache resident nodes, until a block of data reaches a root node resident in the memory storage, wherein the root node has children, but no parent, writing block elements that have reached the root node to the memory storage as an output list of processed data, and populating each parent node with blocks of data from the plurality of nodes which are children of the parent node when the parent node has passed a block upward to a next immediate parent of the parent node.