Interpolation sort algorithm for lists that contain extreme values

الملخص EN

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.