Multiway merge sorter for sorting of large databases

A multiway merge algorithm by using specialized hardware is proposed for sorting a large number of records. By adopting a sorting array that compares k records in parallel and a data-driven control technique that selects k strings for merging, the algorithm performs merge processing for a large number of k-way whose speed is independent of the merge ways. A large number of records can be sorted by iteration of the k-way merge operations. The number of iterations is substantially reduced by increasing the number of merge ways. A compact hardware sorter can be achieved to satisfy both speed and capacity respectively since the sorting array and the working storage can be implemented independently. The database processor RINDA applies the multiway merge sorter for accelerating sorts and joins. The configuration and performance of the sorter are also discussed.