RUN FORMATION IN LARGE SCALE SORTING USING BATCHED REPLACEMENT SELECTION

A large-scale sorting process utilizes a batched replacement selection method to form runs of sorted data records. The batched replacement selection method involves reading multiple records from a persistent data storage into main memory and sorting the multiple records to form a mini-run of multiple sorted data records. After formation, the mini-run is added to a selection tree by inserting a pointer to a first record in the mini-run into the array of pointers. The first record is linked to remaining records in the mini-run. As records are selected for output from the selection tree, the methodology replaces the selected record with a next record in the associated mini-run (if not empty) or alternatively deletes the node if the mini-run is empty. The selected records are collected into an output buffer. When the number of records reaches a pre-determined number, the selected records are written in batch back to the persistent data storage.