Patent Document ID: 9910873
Application ID: 15191893
Patent Status: 1

Claim One:
1. A computer-implemented method to reduce processing overhead in sorting a data set having duplicate values, the computer-implemented method comprising: determining a distribution of values of an unsorted data set that includes a plurality of data records, wherein the distribution specifies a plurality of partitions of the unsorted data set and further specifies, for each partition, an estimate of whether the respective partition consists of duplicates of a respective sort value; partitioning the unsorted data set into the plurality of partitions based on the distribution, wherein each of the data records is inserted into one of the partitions based on a corresponding sort value of the data record, including maintaining, for each partition, a flag indicating whether the respective partition actually consists of duplicates of the respective sort value; upon determining that the estimate that a first of the partitions consists of duplicates is actually false, sub-partitioning the data records of the first partition into uniform and variable sub-partitions, respectively, by operation of one or more computer processors; identifying one or more of the partitions that each contains at least two distinct sort values, the one or more partitions including the first partition; sorting the data records in each of the identified partitions, including sorting the variable sub-partition without sorting the uniform sub-partition, which avoids a processing overhead of sorting the data records in the uniform sub-partition; and subsequent to sorting the data records in each of the identified partitions, generating a sorted data set by merging the plurality of partitions, wherein the sorted data set is output.