Ошибка шины 10 в реализации сортировки слиянием в OS X

Question

Я пытаюсь реализовать сортировку слиянием в C. Написанный мною код работает для списка из 100 000 номеров, но когда я запускаю его в списке из 1 000 000, я получаю "Ошибка шины: 10".

Ошибка возникает, когда я прокомментировал "ОШИБКА ШИНЫ ЗДЕСЬ". Когда возникает ошибка, tmp_list_i == 65920 и pws->merge_cursor == 32776. Функция merge объединяет произвольное количество вложенных массивов, потому что я также использую его для объединения вложенных массивов, отсортированных по разным потокам. Но ошибка шины происходит даже тогда, когда я использую только один поток (то есть, когда нужно объединить только два подмассива).

Есть идеи?

// Represents a sub-array in the list.
typedef struct
{
    int begin_i; // inclusive
    int end_i; // exclusive
    int already_sorted; // if the partition was sorted before runtime
    pthread_t tid; // thread associated with this partition, if any
    int merge_cursor; // index used for merging
} Partition;

// O(n log(n)) 
// n = number of comparisons in a merge
// log(n) = number of merges
void* merge_sort(void* partition)
{
    Partition* part = (Partition*) partition;

    // Base case. One item, so partition is sorted
    int len = part->end_i - part->begin_i;
    if (len < 2)
    {
        part->already_sorted = TRUE;
        return 0;
    }

    // Recursion
    Partition left_part;
    left_part.begin_i = part->begin_i;
    left_part.end_i = part->begin_i + (len / 2);
    left_part.merge_cursor = left_part.begin_i;

    Partition right_part;
    right_part.begin_i = part->begin_i + (len / 2);
    right_part.end_i = part->end_i;
    right_part.merge_cursor = right_part.begin_i;

    merge_sort(&left_part); 
    merge_sort(&right_part); 

    if (left_part.already_sorted && right_part.already_sorted)
        part->already_sorted = TRUE;

    // Create parts array to pass to merge
    Partition* parts[] = {&left_part, &right_part};

    if (merge(parts, 2, len) == FALSE)
        part->already_sorted = FALSE;

    return 0;
}

// O(n) but more specifically O(n * p + n) where p is num_parts
int merge(Partition* parts[], int num_parts, int total_num) 
{
    int already_sorted = TRUE; // whether the partitions were already sorted

    int tmp_list[total_num];
    int tmp_list_i;
    for (tmp_list_i = 0; tmp_list_i < total_num; tmp_list_i++) 
    {
        // find (P)artition (W)ith (S)mallest number under its merge cursor
        Partition* pws = NULL; 

        int parts_i;
        for (parts_i = 0; parts_i < num_parts; parts_i++)
        {
            Partition* this_part = parts[parts_i];

            if (this_part->merge_cursor == MERGE_CURSOR_DONE)
                continue;

            if (pws == NULL)
                pws = this_part; 

            int this_part_num = list[this_part->merge_cursor];
            int smallest_part_num = list[pws->merge_cursor];

            if (this_part_num < smallest_part_num)
            {
                pws = this_part;
                already_sorted = FALSE;
            }
        }

        // add the smallest of the numbers to current spot in tmp array
        tmp_list[tmp_list_i] = list[pws->merge_cursor]; // BUS ERROR HERE

        // increment the merge cursor for pws and set to NULL if done
        (pws->merge_cursor)++;
        if (pws->merge_cursor == pws->end_i)
            pws->merge_cursor = MERGE_CURSOR_DONE;
    }

    // Copy back to list from tmp_list. Costs an extra n.
    int list_i = parts[0]->begin_i; // start where we should in list
    for (tmp_list_i = 0; tmp_list_i < total_num; tmp_list_i++)
    {
        list[list_i] = tmp_list[tmp_list_i];
        list_i++;
    }

    return already_sorted;
}

РЕДАКТИРОВАТЬ: при распределении всего в куче, а не в стеке, я получаю другую проблему. Назначение int this_part_num = list[this_part->merge_cursor]; кажется, не оценивает правильно, и в итоге я получаю ошибку sig:

141             int this_part_num = list[this_part->merge_cursor];
(gdb) s
142             int smallest_part_num = list[pws->merge_cursor];
(gdb) print this_part_num
$5 = 1
(gdb) print list[this_part->merge_cursor]
$6 = 6

Answer 1

Догадаться. Список был объявлен в отдельном файле как int* list но объявлено в файле с функцией merge_sort как extern int list[],