折半插入排序

折半插入排序是一种优化的插入排序算法，它通过利用二分查找来减少比较和交换的次数，从而提高排序效率。

具体实现步骤如下：

1. 将待排序序列分为已排序区间和未排序区间。初始时已排序区间只有一个元素，即第一个元素。
2. 从未排序区间中取出第一个元素，在已排序区间中使用二分查找找到插入位置。
3. 将未排序区间中取出的元素插入到已排序区间中的合适位置。
4. 重复步骤2~3，直到未排序区间中的所有元素都被插入到已排序区间中。

下面是折半插入排序的 Python 实现：

def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        left, right = 0, i - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] > arr[i]:
                right = mid - 1
            else:
                left = mid + 1
        for j in range(i - 1, left - 1, -1):
            arr[j + 1], arr[j] = arr[j], arr[j + 1]
    return arr

在这个实现中，我们使用了两个指针 left 和 right 来表示已排序区间的范围，使用二分查找找到插入位置，然后使用两个 for 循环来完成插入操作。