Binarily Gapped Binary Insertion Sorting Technique

AbstractA Binarily Gapped Binary Insertion Sorting Technique (BGBIST), based on a Binarily Gapped Binary Insertion Sorting Processor (BGBISP), has been described. It performs online real-time sorting of data elements (DEs) as they arrive for being stored in a random access memory (RAM). A modified binary search algorithm has been employed to determine both the correct relative position, i.e. ordering of the DE, and a tentative-gapped absolute position (RAM location) of each arriving DE. At relatively light loading of the RAM, the insertions are nearly collision-free and inter-DE gaps gradually reduce binarily. With increased RAM loading, insertion collisions start increasing, necessitating chain movements of the existing DEs. Each chain movement stops as soon as a gap is reached. The chain movements become more frequent as well as longer as the RAM loading starts becoming high and, consequently, the availability of gaps between the DEs start becoming rarer. The BGBIST sorts fairly large arrays at O(Nlog2 ...