链表原地归并排序遇EXC_BAD_ACCESS，临界数组大小约130760-130770

问题描述 #

对比归并、希尔、快速三种排序算法耗时，其中归并排序采用链表结构实现原地排序（仅切换节点地址，不复制数据）。当目标数组大小超过130760~130770临界值时，递归调用merge方法抛出EXC_BAD_ACCESS(code=2, address=...)异常，小数组无此问题。
异常表现为读取MergeSort实例的错误地址：真实this地址为0x16d4a3448，尝试读取的地址为0x16cca7ff0，二者差值固定为十进制8369240，且常出现在right->next指向空节点时。
尝试修改数组元素类型、监控right->next指向，临界大小未变；新建Clion项目后临界值略有变化但差异不大。需要分析问题原因、解决办法，以及lldb中AddressSanitizer的使用指导。

附原归并排序类代码：

template <typename T>
class MergeSort {
private:
    struct Node {
        T data;
        Node* next;
        Node(T d) : data(d), next(nullptr) {}
    };

    Node* head;
    int size;
    long count = 1;

    void split(Node** head, Node** left, Node** right) {
        Node* fast = *head;
        Node* slow = *head;
        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        *left = *head;
        *right = slow->next;
        slow->next = nullptr;
    }

    Node* merge(Node* left, Node* right) {
        Node* result = nullptr;
        count++;
        if (!left) return right;
        if (!right) return left;
        if (left->data <= right->data) {
            result = left;
            result->next = merge(left->next, right);
        } else {
            result = right;
            result->next = merge(left, right->next);
        }
        return result;
    }

    void mergeSort(Node** headRef) {
        Node* head = *headRef;
        Node* left = nullptr;
        Node* right = nullptr;
        if (!head || !head->next) return;
        split(&head, &left, &right);
        mergeSort(&left);
        mergeSort(&right);
        *headRef = merge(left, right);
    }


public:
    MergeSort() : head(nullptr), size(0) {}

    void insert(T data) {
        Node* newNode = new Node(data);
        newNode->next = head;
        head = newNode;
        size++;
    }

    void sort() {
        mergeSort(&head);
        std::cout << "Total merge count: " << count << std::endl;
    }

    void override(T arr[]) {
        Node* current = head;
        int i = 0;
        while (current) {
            arr[i++] = current->data;
            current = current->next;
        }
    }
};

问题原因分析 #

核心问题是递归版merge导致的栈溢出：

• 归并排序本身的递归深度为O(logN)，但你实现的merge方法采用递归方式，其递归深度会达到O(N)（例如当链表完全逆序时，每次merge都会递归处理剩余的整个子链表）。
• 系统默认栈空间有限（通常为8MB左右），当链表长度达到13万时，递归调用的栈帧累积超过栈空间上限，导致栈溢出。栈溢出会破坏栈上的关键数据（如函数返回地址、类实例的this指针），进而引发读取错误地址的EXC_BAD_ACCESS异常。

解决办法 #

将递归版merge改为迭代实现，避免递归带来的栈帧累积问题。迭代版merge仅使用固定数量的栈上变量，递归深度不再依赖链表长度。

修改后的merge函数示例：

Node* merge(Node* left, Node* right) {
    count++;
    // 哨兵节点简化边界处理
    Node dummy(T{});
    Node* current = &dummy;

    while (left != nullptr && right != nullptr) {
        if (left->data <= right->data) {
            current->next = left;
            left = left->next;
        } else {
            current->next = right;
            right = right->next;
        }
        current = current->next;
    }

    // 拼接剩余未处理的节点
    current->next = left != nullptr ? left : right;

    return dummy.next;
}

修改后，归并排序的递归深度回到O(logN)，即使链表长度达到百万级也不会触发栈溢出。

AddressSanitizer使用指导（Clion环境） #

AddressSanitizer可检测栈溢出、野指针、内存泄漏等多种内存错误，在Clion中的配置步骤如下：

1. 进入Run -> Edit Configurations
2. 选中当前运行的程序配置，找到CMake options，添加编译参数：-fsanitize=address -g（-g用于生成调试信息，方便定位错误）
3. （可选）在Environment variables中添加：ASAN_OPTIONS=detect_stack_use_after_return=1，开启栈溢出的严格检测
4. 点击Apply保存配置，重新编译运行程序
5. 当程序触发内存错误时，AddressSanitizer会在控制台输出详细的错误报告，包括错误类型、完整调用栈、出错代码行，直接定位问题根源

注意：启用AddressSanitizer后程序运行速度会下降，内存占用增加，仅用于调试阶段，发布版本需关闭该选项。

内容的提问来源于stack exchange，提问作者dannydoor