仿照教材代码，使用顺序表实现折半插入排序算法，并在主函数中输入元素，再输出排序结果（需要用到顺序表的各种基本运算） 将代码直接

折半插入排序是一种改进的插入排序算法，它通过二分查找的方式找到插入位置，减少了比较次数。下面是一个简单的顺序表实现的折半插入排序示例，假设我们有一个`ListNode`结构表示顺序表节点：

#include <iostream>

// 定义顺序表节点
struct ListNode {
    int data;
    ListNode* next;
    ListNode(int val) : data(val), next(nullptr) {}
};

// 顺序表的基本操作
ListNode* create_list(int* arr, int size) {
    ListNode* head = nullptr;
    for (int i = 0; i < size; ++i) {
        head = insert(head, arr[i]);
    }
    return head;
}

ListNode* insert(ListNode* head, int value) {
    if (!head || head->data > value) {
        head = new ListNode(value);
    } else {
        ListNode* current = head;
        while (current->next && current->next->data < value) {
            current = current->next;
        }
        current->next = new ListNode(value);
    }
    return head;
}

// 折半插入排序
void binary_insertion_sort(ListNode** head, int size) {
    if (size <= 1) {
        return;
    }

    // 找到中间元素
    int mid = size / 2;
    ListNode* middle = get_middle(head);

    // 对中间及以后的部分应用插入排序
    binary_insertion_sort(&middle, size - mid);

    // 将已排序部分与剩余部分合并
    merge(head, middle);
}

// 中间元素操作
ListNode* get_middle(ListNode* head) {
    if (!head || !head->next) {
        return head;
    }
    ListNode* slow = head;
    ListNode* fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// 合并两个有序链表
void merge(ListNode** head, ListNode* tail) {
    ListNode dummy(0), *current = &dummy;
    while (*head && tail) {
        if (*head->data <= tail->data) {
            current->next = *head;
            head = &(*head)->next;
        } else {
            current->next = tail;
            tail = tail->next;
        }
        current = current->next;
    }
    if (*head) {
        current->next = *head;
    } else {
        current->next = tail;
    }
    *head = dummy.next;
}

// 主函数
int main() {
    int arr[] = {9, 5, 7, 2, 6, 8};
    int n = sizeof(arr) / sizeof(arr[0]);

    ListNode* list = create_list(arr, n);
    std::cout << "Original array: ";
    print_list(list);

    binary_insertion_sort(&list, n);
    std::cout << "\nSorted array after insertion sort: ";
    print_list(list);

    return 0;
}

// 辅助函数：打印顺序表
void print_list(ListNode* head) {
    while (head) {
        std::cout << head->data << " -> ";
        head = head->next;
    }
    std::cout << "nullptr\n";
}