在OS X上的合併排序實現中的總線錯誤10

Question

我想在C中實現合併排序。我編寫的代碼適用於100,000個數字的列表，但是當我在1,000,000列表上運行它時， 「總線錯誤：10」。

錯誤發生在我評論過「BUS ERROR HERE」的地方。發生錯誤時，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[]的文件中聲明。