Patent ID: 6181678
Filing Date: 2001-01-30
Classification: G06F,Y10S

Abstract:
Device for sorting data elements each including a respective sort key, comprising:storage means organized according to a binary tree with 2.sup.n -1 nodes numbered from 1 to 2.sup.n -1 which are each able to contain a data element and are distributed in n successive stages numbered from 0 to n-1, whereby stage q comprises nodes 2.sup.q to 2.sup.q+1 -1; andmeans of control of the binary tree for dispersing data elements to be sorted within the tree in such a way as to satisfy an ordering condition according to which, for each integer i lying between 1 and 2.sup.n-1 -1 such that node i contains an element to be sorted, each of the nodes 2i and 2i+1 either contains no element to be sorted, or contains an element having a sort key greater than or equal to, in the sense of a determined order relation, the sort key of the element contained in node i,wherein the means of control respond to commands to modify the contents of the binary tree which include commands for inserting a new element to be sorted,wherein the means of control comprise m successive controllers each associated with a stage or with a plurality of consecutive stages of the binary tree, m being an integer lying between 2 and n, and n-1 interface registers between successive stages, among which each of the m-1 interface registers between stage pairs associated with different controllers constitutes a pipeline register, and wherein each command for modifying the contents of the binary tree is propagated from stage 0 to stage n-1 by means of the interface registers, the pipeline register or registers allowing parallel working of the controllers.