Merge sort enhanced in place sorting algorithm

This paper aims at introducing a new sorting algorithm which sorts the elements of an array In Place. This algorithm has O(n) best case Time Complexity and O(n log n) average and worst case Time Complexity. We achieve our goal using Recursive Partitioning combined with In Place merging to sort a given array. A comparison is made between this particular idea and other popular implementations. We finally draw out a conclusion and observe the cases where this outperforms other sorting algorithms. We also look at its shortcomings and list the scope for future improvements that could be made.

I. Introduction

In mathematics and computer science, the process of ar-ranging similar elements in a definite order is known as sorting. Sorting is not a new term in computing. It finds its significance in various day to day applications and forms the backbone of computational problem solving. From complex search engine algorithms to stock markets, sorting has an impeccable presence in this modern day era of information technology. Efficient sorting also leads in optimization of many other complex problems. Algorithms related to sorting have always attracted a great deal of Computer Scientists and Mathematicians. Due to the simplicity of the problem and the need for solving it more systematically, more and more sorting algorithms are being devised to suit the purpose.