Computer with two-dimensional merge tournament sort using offset-value coding
US5487166A · kind A · utility
Assignee
Inventor
Key dates
| Filing date | Sep 19, 1994 |
| Grant date | Jan 23, 1996 |
| Priority date | — |
| Expiry date | Sep 19, 2014 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2207/224
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
To perform a sort of N records, a two-dimensional tree structure is formed with a tree of subtrees, where each subtree is formed by a plurality of nodes organized in a binary tree. For each leaf node in the tree, there is an ancestor chain of nodes (from child to parent, from parent to grand-parent, from grand-parent to great-grand-parent, . . . and so on) that connects each leaf node to the root node. To perform the sort, the processing unit stores codes representing keys into nodes in the two-dimensional tree and performs a tree sort of the keys using the codes. The codes are accessed in the subtrees and processed to determine the sort order of the keys and therefore the sort order of the corresponding records.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.