Parallel merge sort method and apparatus
US5852826A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Jan 26, 1996 |
| Grant date | Dec 22, 1998 |
| Priority date | — |
| Expiry date | Jan 26, 2016 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99937
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
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…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.