Brownian Motus and Clustered Binary Insertion Sort methods: An efficient progress over traditional methods

Sorting is the basic operation in every application of computer science. The paper proposes two novel sorting algorithms based on the concept of traditional Insertion Sort (IS). Firstly, Brownian Motus Insertion Sort (BMIS) based on IS is proposed. It is followed by Clustered Binary Insertion Sort (CBIS) based on the principles of Binary Insertion Sort (BIS). BIS is a binary search enhancement of IS which is a quite famous variant of it. Average case time complexity of BMIS is O(n0.54); and that of CBIS is O(nlogn). The scenario which results into the worst case of IS is with the complexity of O(n2); and BIS with O(nlogn) is the best case scenario for BMIS and CBIS with complexity of O(n). The probability of getting a worst case scenario for BMIS and CBIS is approximately zero. Comparison of proposed algorithms with IS and BIS has been performed at 25%,50%,75% and100% level of randomness in the initial dataset. These results lead to prove our claim of devising efficient enhancements of IS. The results further reveal that performance of BMIS and CBIS will increase with a decrease in randomness level of the dataset in comparison to its counterparts. The number of comparisons required by BMIS and CBIS will approach to O(n) with randomness level approach to zero. So, for nearly sorted datasets, our proposed BMIS and CBIS are the best choice. Both BMIS and CBIS are in-place, stable and online sorting algorithm.