Abstract—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.
Index Terms—Sorting algorithm, interpolation, sub-arrays, time complexity, strings.
Gourav Saha is with the Madras Institute of Technology, Anna University, India (e-mail: email@example.com).
Cite: Gourav Saha and S. Selvam Raju, "Interpolation Sort and Its Implementation with Strings," International Journal of Computer Theory and Engineering vol. 4, no. 5, pp. 772-776, 2012.