Sorting and searching data have several applications in the database and analytics domains. Sorting operations involve reordering data in a particular order, and a conditional search operation may involve retrieving a particular entry from the sorted data. Responding to queries to the database, ranking these responses based on their relevance or other metrics, and determining the most frequently accessed entries are some of the operations that may depend on such sorting and conditional searching. These operations usually involve processing large amounts of data.
Data is conventionally fetched from a storage device, such as memory or caches, to a general purpose computation module (usually a processor), which carries out the sort and search operations. One algorithm used for sorting is the Batcher's Odd-Event Sort. Existing software and hardware implementations of this sort algorithm have several limitations and drawbacks, including, for example, large overhead, slow speed, and high cost.
Batcher's Odd-Event Sort may be implemented, for an array of n elements X1 to Xn, as follows. An odd-even pair may be defined as a first element having an odd subscript, and a next element having an even subscript. In a first step of the sort operation, every element with an odd subscript, i.e., X1, X3, . . . , is compared with its respective successor element having an even subscript, i.e., X2, X4, . . . . For any given comparison, in the case of an ascending sort operation, if the odd element is greater than the even element, the two elements are swapped. This operation is performed for every odd-even pair in the array. In a second step, every element with an even subscript is compared with its successor element with an odd subscript, and their values are swapped if the element with the even subscript is larger. This operation is performed for every even-odd pair in the array. The operations of the first and second steps are repeated, alternately, until the entire array is sorted.