Parallel merge sort method and apparatus

摘要

A parallel sorting technique for external and internal sorting which maximizes the use of multiple processes to sort records from an input data set. Performance of the sort linearly scales with the number of processors because multiple processors can perform every step of the technique. To begin, the records of a data set to be sorted are read from an input file and written into multiple buffers in memory so long as memory is available. The records within each buffer are then simultaneously sorted to create runs therein. A merge tree is constructed with the runs as stream elements into leaf nodes of the tree, where the stream elements are merged. The stream elements at each node are then merged by multiple processes working simultaneously at the node, thereby generating an output stream of elements for merging at a higher node. For an internal sort, the run that results from all of the merging is immediately written to an output device. For an external sort, the run is an intermediate run, written to secondary storage along with other intermediate runs. A forecast structure provides a forecast of the order of the run blocks from the multiple intermediate runs. These blocks are read in the forecasted order from secondary storage, written into memory and merged through a merge tree to form an ordered record stream that is a complete run for the data set. The ordered record stream is then written to the output device.