In a data storage system in which there can be multiple references to a
single instance of an object, a method for regenerating the number of
references to each object instance. The method includes radix sorting the
references to the objects to generate a reference list, counting the
references to each unique object and merging the counts with the object
descriptions, placing the count of the number of references to each
object into the respective object description. The sorting, counting and
merging techniques used by this method generate sequential memory access
patterns that enable efficient use of low-cost memory and block-oriented
memory access interconnect fabric protocols. Furthermore, multiple
instances of the sorting, counting and merging processes can be used in
parallel to reduce the time required to regenerate the reference counts
for a large number of objects.