数据结构折半插入排序，写出代码实现

折半插入排序（Binary Insertion Sort）是插入排序的一种优化版本，特别适用于部分有序的数据。它利用了数组元素大致有序的特性，通过每次将待插入的元素与已排序部分的中间元素进行比较，从而将插入操作分成了两半，从而减少了比较和移动的次数。这种算法的时间复杂度在最好情况下（输入数据完全有序）仍为O(n^2)，但在接近有序的情况下，性能会有显著提升。

以下是折半插入排序的Python代码实现：

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

    # 分治策略
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # 递归地对左半部分进行折半插入排序
    binary_insertion_sort(left_half)

    # 插入操作
    i = mid - 1  # 已排序部分的右边界
    for value in reversed(right_half):  # 从大到小处理右半部分
        while i >= 0 and value < arr[i]:
            arr[i + 1] = arr[i]  # 将大的元素向右移动
            i -= 1
        arr[i + 1] = value  # 插入当前值
        i += 1

    return arr