An Efficient O(N) Comparison-Free Sorting Algorithm

Abstract

In this paper, we propose a novel sorting algorithm that sorts input data integer elements on-the-fly without any comparison operations between the data comparison-free sorting. We present a complete hardware structure, associated timing diagrams, and a formal mathematical proof, which show an overall sorting time, in terms of clock cycles, that is linearly proportional to the number of inputs, giving a speed complexity on the order of O(N). Our hardware-based sorting algorithm precludes the need for SRAM-based memory or complex circuitry, such as pipelining structures, but rather uses simple registers to hold the binary elements and the elements’ associated number of occurrences in the input set, and uses matrix-mapping operations to perform the sorting process. Thus, the total transistor count complexity is on the order of O(N).

Existing System

Randomized Sorting, Recursive Algorithm.

Proposed System

In this paper, we proposed a novel mathematical comparison-free sorting algorithm and associated hardware implementation. Our sorting algorithm’s main features and contributions include as follows. Our design affords continuous sorting of input element sets, where each set can hold any type and distribution (ordering) of data elements. Sorting is triggered with a start-sort signal and sorting ends when a done sorting signal is asserted by the design, which subsequently begins sorting the next input set, thus affording continuous, end-to-end sorting. 2) Our sorting design does not require any ALU comparisons/shifting-swapping, complex circuitry, or SRAM-based memory, and processes data in a forward moving direction through the circuit. Our design’s simplicity results in a highly linearized sorting method with a CMOS transistor count that grows on the order of O(N). Hence, the design provides low and efficient power components with the addition of regularity and scalability as key structure features, which provide easily and quick miagration to embedded micro-controllers and field-programmable gate arrays (FPGAs). The sorting delay time is always linearly proportional to the number of input data elements N, with upper and lower bounds of 3N and 2N clock cycles, respectively, giving a linear sorting delay time of O(N). This sorting time is independent of the input elements’ ordering or repitition since the design always performs the same operations within these bounds as opposed to Quicksort and other sorting algorithms, which have large and nonlinear margin of bounds.

Architecture

Write-evaluate Phase

Read-sort phase