Method and device for insert sorting

Abstract

The present invention discloses an inserting-ordering method, which is used to insert keywords of the data to be inserted into the queue list according to the ordering rule of the keywords of node data in the queue list. The present invention comprises the following steps of comparing the keywords of each node data in specified queue list with that of data to be inserted, conducting shifting operation for the node data in specified queue list according to the comparing results, and inserting the data to be inserted into the specified queue list while conducting shifting operation. The adoption of the present invention completes comparing, shifting and inserting operation in a clock period and cancels reverse shifting logic, which ensures that the sequencer adopting the inserting-ordering method can realize linear operation, simplifies the design of sequencer and expands the application of the sequencer.

Description

technical field [0001] The invention relates to the field of electronic technology, in particular to a method and device for insertion sorting. Background technique [0002] At present, sequencers are often used in large-scale integrated circuit design. For example, in switching networks, the sequencer selects the shortest or longest queue, the highest or lowest priority, and the data packet with the longest or shortest queuing time. [0003] Among them, the interpolation sequencer is a circuit that is often used. The principle of insertion sorting is: each time a value to be sorted, such as: data or a keyword, is inserted into the appropriate position in the previously arranged sequence of length N according to its size, and a sequenced sequence is obtained A sequence of length N+1. Repeat the above steps until all values ​​are completely inserted. Assume that the values ​​to be sorted are stored in the array R[1,...,n]. Initially, R[1] forms a sequence by itself, from ...

AI Technical Summary

Problems solved by technology

[0010] Although the existing sorter can complete the sorting function, but the sorting speed is relatively low, sorting every two clock cycles

In some applications that have higher requirements for sorting speed, the sorting circuit cannot be fully qualified

Especially in applications that require real-time processing of data, the existing sorter will completely become a bottleneck

[0011] Therefore, the disadvantages of the prior art are: the sorting speed of the sorter is low, it cannot be used in occasions with high requirements for sorting speed, and cannot meet the requirements of real-time data processing Require

Images