Parallel data sorting

Abstract

Techniques for high-performance parallel data sorting are provided. K, M, and N exceed 1. In a first phase, a plurality of unordered data elements to be sorted is divided into K unordered lists each preferably having approximately M elements. Each of these K unordered lists can be independently sorted in parallel using any algorithm, such as quicksort, to generate K ordered lists. In a second phase, N balanced workloads are determined from the K ordered lists by using an iterative converging process capped by a maximum number of iterations. Thus, any non-uniform or skewed data distribution can be load balanced with minimal processing time. Once the N balanced workloads are determined, they can be independently sorted in parallel, for example by using a merge sort, and then combined with a fast concatenation to provide the final sorted result. Thus, sorting operations are fully parallelized while avoiding expensive data scanning steps.