A Dynamic Look-Ahead Approach to Sorting in a Big Data Age

A procedure that reduces the data movement requirements of the Quicksort algorithm is presented. The key feature of this procedure is that for every recursion, except the first, the data in a sub-node receives an inheritance from the parent node that reduces both the number of required key comparisons and the number of interchanges or swaps. It is mathematically demonstrated that, at each level of the sort tree, the new procedure requires only approximately four ninths as much data movement as the standard Quicksort implementation.