Method and apparatus for sorting elements

A method for sorting comprising the steps:

• forming a decision tree comprised of N levels, where N.gtoreq.-1 and is an integer and corresponds to a queue of 2.sup.N elements each having a value, as the queue is filled, each level L having 2.sup.L entries where L.gtoreq.0 and is an integer, each entry having either a first result or a second result corresponding to values in the queue;
• reading the results in the entry of the 0th level;
• reading the results in the entries of subsequent higher levels, if any, depending on the result read in a previous lower level;
• and
• choosing the value from the queue corresponding to the result in the entry in a highest level.

An apparatus for sorting comprising:

• an array E of size 2.sup.N where elements are stored and where N.gtoreq.1 and is an integer, with the elements in array E indexed from 0 to 2.sup.N -1;
• a first memory maintaining a value NE equal to how many elements are stored in the array E;
• a decision tree of 2.sup.N -1 bits, where the number of bits in its part I is 2.sup.N /2.sup.I+1, which describes the relative ordering of elements in array E;
• a comparison list array CL of size N, where CL›i! contains a value of a lower element within E›l! and E›h! where:
• ##EQU4## a second memory maintaining a value L equal to the value of a last element in the array E;
• and
• a controller which inserts elements into array E in contiguous memory locations in an unsorted manner, modifies the decision tree to describe the relative ordering of the elements of the array E, modifies the array CL so CL›i! contains the value of the lower element within E›l! and E›h!;
• updates the value L with the value of each new element added to the array E, and updates the value NE as each new element is added to the array.

A method for manipulating elements comprising the steps of:

• storing a first element having a value in a first queue location in an element queue having a size which stores 2.sup.N elements, where N.gtoreq.2 and is an integer;
• updating in a register how many elements are in the queue and the value of the first element;
• storing a second element having a value in a second queue location of the element queue contiguously with the first element;
• updating in the register how many elements are in the queue and the value of the second element;
• comparing the value of the second element with the value of the first element to yield a first comparison result corresponding to which value of the first and second elements is larger;
• storing a first comparison result in a first location of a plurality of locations of a decision tree, said plurality of locations corresponding to a plurality of levels;
• updating a first comparison element of a plurality of comparison elements of a comparison list array, each comparison element associated with a level of the plurality of levels, the comparison element updated corresponding to the second queue location of the element queue in which the second element is stored and in the first queue location of the element queue in which the first element is stored;
• storing a third element having a value in a third queue location in the element queue contiguously with the second elements;
• updating in the register how many elements are in the queue and the value of the third element;
• comparing the value of the third element with the value of the first and second elements which is smaller to yield a second comparison result corresponding to which value of the first and second elements and the third element is smaller;
• storing the second comparison result in a second location of the decision tree;
• updating a second comparison element corresponding to the third queue location in which the third element is stored;
• storing a fourth element having a value in a fourth queue location in the element queue contiguously with the third element;
• updating in the register how many elements are in the queue and the value of the fourth element;
• comparing the value of the fourth element with the third element to yield a third comparison result corresponding to which value of the third and fourth elements is smaller;
• storing the third comparison result in a third location of the decision tree;
• comparing the value of the third element and fourth element which is smallest with the value of the first element and second element which is smallest to yield a fourth comparison result corresponding to which value of the first, second, third or fourth elements is smaller;
• storing the fourth comparison result in the second location of the decision tree;
• updating the comparison list;
• changing the value of the third element in the element queue to a new value;
• comparing the new value to the value of the fourth element to yield a fifth comparison result;
• storing the fifth comparison result in the third location of the decision tree;
• comparing the fifth comparison result with the first comparison result of the decision tree to obtain a sixth comparison result;
• storing the sixth comparison result in the second location of the decision tree;
• updating the comparison list;
• finding the queue location in the element queue which has the smallest value by only reading the comparison result in the decision tree;
• and
• obtaining the smallest value.