Techniques are disclosed for sorting an input data set. A sort tool determines a distribution of values of a data set that includes a plurality of data records. The sort tool partitions the data set into a plurality of subsets based on the distribution. Each of the data records is inserted into one of the subsets based on a corresponding sort value of the data record. The sort tool identifies one or more of the subsets that contain at least two distinct sort values. In each of the identified subsets, the data records are sorted by a corresponding sort value of the data record.