Patent ID: 6065005
Filing Date: 2000-05-16
Classification: G06F,Y10S

Abstract:
A method for operating a data processing system having a plurality of processors to sort a set of data records each having an associated key for governing the sort process, the method comprising:determining a range for the key values by sampling the key values;dividing the range into a plurality of quantiles, one for each processor, each quantile having a respective index;at each processor, defining a plurality of buckets, each bucket corresponding to a respective one of a plurality M.sub.p of subintervals in the quantile, each subinterval having a respective index;determining directly from each key value using fast operations the index of the quantile in which the key value lies and the index of the subinterval in which the key value lies;distributing each key to the processor corresponding to the quantile in which the key value lies;at each processor distributing the keys falling in the quantile corresponding to the processor into the buckets according to the indices of the subintervals in which the key values lie and processing the buckets in sequence in order to sort the records, sorting the keys in each bucket if the bucket contains more than one key; andconcatenating the sorted keys from each processor.