Interpolation sort algorithm for lists that contain extreme values

Abstract

  This paper describes a technique for applying interpolation sort algorithm on lists that contain  extreme values. The traditional interpolation algorithm costs O(n) time and space complexity, where n is number of elements in the list, but with drawback of its limitation of application on just  lists contain no extreme values. The proposed technique adapt the algorithm to sort  list contain extreme  values by reindex it and reformulate  the linear interpolation formula.