merge_sort（）中的merge（）如何工作？

Question

所以我在看Rosetta Code的合併排序的C示例，我對merge（）函數的工作原理有點困惑。我認爲這是他們使用的語法將我帶到冒號和？的。

void merge (int *a, int n, int m) { 
    int i, j, k; 
    int *x = malloc(n * sizeof (int)); 
    for (i = 0, j = m, k = 0; k < n; k++) { 
     x[k] = j == n  ? a[i++] 
      : i == m  ? a[j++] 
      : a[j] < a[i] ? a[j++] 
      :    a[i++]; 
    } 
    for (i = 0; i < n; i++) { 
     a[i] = x[i]; 
    } 
    free(x); 
} 

void merge_sort (int *a, int n) { 
    if (n < 2) 
     return; 
    int m = n/2; 
    merge_sort(a, m); 
    merge_sort(a + m, n - m); 
    merge(a, n, m); 
} 

merge（）函數的for循環究竟發生了什麼？有人可以解釋嗎？

Answer 1

閱讀評論：

void merge (int *a, int n, int m) { 
    int i, j, k; 
    // inefficient: allocating a temporary array with malloc 
    // once per merge phase! 
    int *x = malloc(n * sizeof (int)); 
    // merging left and right halfs of a into temporary array x 
    for (i = 0, j = m, k = 0; k < n; k++) { 
     x[k] = j == n  ? a[i++] // right half exhausted, take from left 
      : i == m  ? a[j++] // left half exhausted, take from right 
      : a[j] < a[i] ? a[j++] // right element smaller, take that 
      :    a[i++]; // otherwise take left element 
    } 
    // copy temporary array back to original array. 
    for (i = 0; i < n; i++) { 
     a[i] = x[i]; 
    } 
    free(x); // free temporary array 
} 

void merge_sort (int *a, int n) { 
    if (n < 2) 
     return; 
    int m = n/2; 
    // inefficient: should not recurse if n == 2 
    // recurse to sort left half 
    merge_sort(a, m); 
    // recurse to sort right half 
    merge_sort(a + m, n - m); 
    // merge left half and right half in place (via temp array) 
    merge(a, n, m); 
} 

一種更簡單，更高效的版本merge功能，只用一半的臨時空間：

static void merge(int *a, int n, int m) { 
    int i, j, k; 
    int *x = malloc(m * sizeof (int)); 
    // copy left half to temporary array 
    for (i = 0; i < m; i++) { 
     x[i] = a[i]; 
    } 
    // merge left and right half 
    for (i = 0, j = m, k = 0; i < m && j < n; k++) { 
     a[k] = a[j] < x[i] ? a[j++] : x[i++]; 
    } 
    // finish copying left half 
    while (i < m) { 
     a[k++] = x[i++]; 
    } 
} 

的merge_sort的更快版本包括分配一個臨時的數組x的大小爲n * sizeof(*a)，並將其傳遞給遞歸函數merge_sort1，該函數調用merge，並將其作爲額外的參數，作爲w埃爾。在merge的邏輯也與此一半多的比較改善上i和j：

static void merge(int *a, int n, int m, int *x) { 
    int i, j, k; 

    for (i = 0; i < m; i++) { 
     x[i] = a[i]; 
    } 
    for (i = 0, j = m, k = 0;;) { 
     if (a[j] < x[i]) { 
      a[k++] = a[j++]; 
      if (j >= n) break; 
     } else { 
      a[k++] = x[i++]; 
      if (i >= m) return; 
     } 
    } 
    while (i < m) { 
     a[k++] = x[i++]; 
    } 
} 

static void merge_sort1(int *a, int n, int *x) { 
    if (n >= 2) { 
     int m = n/2; 
     if (n > 2) { 
      merge_sort1(a, m, x); 
      merge_sort1(a + m, n - m, x); 
     } 
     merge(a, n, m, x); 
    } 
} 

void merge_sort(int *a, int n) { 
    if (n < 2) 
     return; 
    int *x = malloc(n/2 * sizeof (int)); 
    merge_sort1(a, n, x); 
    free(x); 
}