Method and apparatus for high speed streaming sorter

Abstract

Sorting algorithms are generally used at different steps in data processing. In many situations, the efficiency of the sorting algorithm used determines the throughput/execution speed of the application. Methods for implementing high speed sorting in hardware are often based on Batcher's Odd/Even sort or Bitonic sort algorithms. These algorithms are computation intensive and involve high number of logic gates to implement and high power consumption. The higher the number of logic gates, the more silicon area may be required and may lead to higher cost. Insertion sort is a sorting algorithm that is relatively simpler and may require fewer logic gates to implement. However, throughput achieved using Insertion sort algorithm is much lower than the throughput achieved using high speed sorting algorithms. A method and apparatus enable an efficient hardware design capable of simultaneously sorting multiple data inputs for high throughput at reduced complexity.