写一个折半插入排序代码

折半插入排序是一种改进的插入排序算法，它通过将数组分为两部分，一部分已经排序，另一部分未排序，然后每次从未排序部分选择中间元素，将其插入到已排序部分的适当位置，直到整个数组有序。以下是使用Python实现的折半插入排序的代码：

def binary_insertion_sort(arr):
    if len(arr) <= 1:
        return arr

    def _insertion_sort(start, end):
        while start < end:
            mid = (start + end) // 2
            if arr[mid] > arr[end]:
                # 如果中间元素大于末尾元素，则交换它们的位置
                arr[start], arr[mid] = arr[mid], arr[start]
                start = mid
            else:
                end = mid

    # 首先对整个数组进行排序
    for i in range(1, len(arr)):
        _insertion_sort(0, i)

    return arr

# 示例
arr = [9, 5, 2, 7, 4, 6, 8, 1, 3]
sorted_arr = binary_insertion_sort(arr)
print("Sorted array:", sorted_arr)