Efficient Sort Using Modified Binary Search-a New Way to Sort
Masood Ahmad, Ataul Aziz Ikram, Ishtiaq Wahid, Abdu Salam, Abdul Wali · 2013
3 Abstract: In a single iteration of Insertion sort, only one element is inserted to its proper position. In this technique the proper position of the item can be found using linear search algorithm starting from first element and proceed in incremental fashion. The linear search can be applied either in incremental fashion or in reversed order to find the proper position of the element in the sorted part of the array. So it takes a huge amount of time to search an item when the size of the array is very large. In the proposed technique, binary search instead of linear search is used to find the proper place of an item in the array. Binary search is applicable because the part of the array in which the new element is to be inserted is in sorted form. Similarly the average case running time is further reduced such that the new element to be inserted is first compared with last element of sorted part of the array. If it is greater than the last value of sorted part of the array, no need to perform binary search because the element is in its proper place. Similarly if the element of interest is less than last element of sorted part of the array then it is also compared with the very first element of the array. If it is less than the first element, then binary search cannot be performed and the element is inserted to the first position of the array. The proposed algorithm is compared with insertion sort, binary insertion sort and shell sort. Simulation results show that it is better than existing techniques.