写一段插值法排序算法代码

插值法排序算法是一种基于插值查找的排序算法，其基本思想是根据元素的大小关系，将序列分为有序和无序两部分，每次将无序部分中的一个元素插入到有序部分中适当位置，直到整个序列有序为止。

下面给出一个简单的插值法排序算法的示例代码：

def interpolation_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        low = 0
        high = i - 1
        while low <= high:
            mid = low + int((key - arr[low]) * (high - low) / (arr[high] - arr[low]))
            if key < arr[mid]:
                high = mid - 1
            else:
                low = mid + 1
        for j in range(i - 1, low - 1, -1):
            arr[j + 1] = arr[j]
        arr[low] = key
    return arr

在这段代码中，我们使用了插值查找的思想，在确定插入位置时，根据元素的值与已排序部分的端点值之间的比例来计算索引值，从而尽可能地减少比较次数，提高排序效率。