Interpolation Sort and its Implementation with Strings

摘要

In this paper we propose a new array sorting algorithm with average and best time complexity of O (n). Its best, worst and average time complexity has been analysed. Also the difficulty of applying this algorithm with strings has been discussed and its solution too is found. The limitation of the solution is also analysed.