1. A method comprising: determining a distribution of values of a data set that includes a plurality of data records; partitioning the data set into a plurality of subsets based on the distribution, wherein each of the data records is inserted into one of the subsets based on a corresponding sort value of the data record; identifying one or more of the subsets that contain at least two distinct sort values; and sorting, in each of the identified subsets, the data records by a corresponding sort value of the data record.