Binarily Gapped Binary Insertion Sorting Technique

Abstract

A 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(Nlog₂ N) up to moderate loading of the RAM. It is also amenable to a relatively simple hardware implementation.

KEYWORDS:

• Binary insertion sorting
• Binarily gapped binary insertion sorting
• Binary search processor
• Binarily gapped binary insertion sorting processor
• Gapped insertion sorting

Additional information

Notes on contributors

Swapan Kumar Ray

Swapan Kumar Ray received the BTelE and the MTech (EE) degrees from Jadavpur University, Calcutta, and the Indian Institute of Technology, Kanpur, in 1965 and 1967, respectively. After serving for two years as an electronics engineer at the Physical Research Laboratory, Ahmedabad, he joined Jadavpur University in 1969 as a computer engineer in the erstwhile Computer Centre and later became a professor in the newly created Computer Science and Engineering Department in 1988. Professor Ray spent the academic year 1980–1981 at the Polytechnic Institute of New York (Polytechnic University) as a Fulbright Fellow and acted as a Session Chairman in the IEEE TENCON'87 Conference held in Seoul, Korea, in 1987. He was an Emeritus Fellow of the University Grant Commission, Government of India during 2011–2013. He is the author of approximately 45 technical papers published in reputable national and international journals and conference proceedings. Professor Ray is a Fellow of the IETE (India) and the IE (India), a Senior Member of the IEEE, and is listed in Marquis’ Who's Who in the World.

E-mail: [email protected]

Surajeet Ghosh

Surajeet Ghosh is presently holding the post of assistant professor in the Department of Computer Science & Technology, Indian Institute of Engineering Science and Technology, Shibpur, Howrah, India. He received the Doctoral Degree in Engineering from Jadavpur University, Kolkata. He received his BTech degree in Computer Science and Technology from Kalyani University and Masters in Engineering in Computer Science and Engineering from West Bengal University of Technology, Kolkata. He has received IETE-Gowri Memorial Award 2008 and Best Paper Award at IEEE International Conference on Computational Intelligence and Computing Research (IEEE ICCIC) 2013. He acted as a Session Chairman in the IEEE ANTS 2015 Conference held in Kolkata, India, in 2015. He is a Life Member of IETE, Member of IEEE and IEEE Computer Society. His current research interests are in computer architecture, computer network, bioinformatics, and embedded systems.

E-mail: [email protected]