I tried to compare the time spent on sorting of 3 algorithms: merge, shell, quick. For the merge sorting, I implemented linked list with struct for the in-place sorting - just switching the address of each node, not copying and paste the data.

However, when the target array size exceeds the particular number - it is around 130760~130770 - it throws error of EXC_BAD_ACCESS(code=2, address= ... ) when it calls merge method recursively. The size does matter because the lesser size doesn't reproduce the exception.

The code of merge sorting class is the following:

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;
        }
    }
};

The exception came from reading of the wrong address of MergeSort instance itself.

enter image description here

In this case, the real address of "this" was 0x16d4a3448, and the address attempted to read was 0x16cca7ff0.

I figured out that the difference of the two address was always 8369240 in decimal number when the error was thrown, which is a pretty interesting number.

The problem was also always occurred when the node pointing null was close to the "right->next".

I also tried changing the type of elements of array but it didn't change the critical size of array. So the stack overflow might not be the problem.

It seems that for some reason it reads wrong address of instance if the size of array exceeds some fixed value, but I have no idea why this is happening to me.

For your information, I'm currently working with Clion 2022.3.1 on M1 macbook air.

I tried changing the type of elements and monitoring what right->next points to. It both didn't affect the critical size pretty much.

I also made another project in the Clion and it changed the critical size a bit, not much.

I found that using AddressSanitizer of lldb would be helpful for the monitoring memory leakage, but I couldn't figure out how to use it. If you can give me some information, please. (I'm not friendly with debugging tools because I don't major in CS, just beginner)

Thank you in advance.

CodePudding user response：

The merge function calls itself for every node that is merged. This will lead to stack overflow for large lists. Change merge() to be iterative.