意外的困境與自上而下的合併排序

Question

我剛剛完成了關於自下而上合併排序的要點，在我看來，它是有道理的，但是當我想到如何執行它時，會讓我有點困惑。

我知道我們是通過組合相鄰的元素對來開始的，但是如何在合併它們之前比較元素的大小呢？這不會最終成爲一個n^2算法嗎？

例如：

可以說我有一個數組像這樣：

int a[6] = {1,3,2,6,8,7}; 

然後，我把它分解成大小1（不是真的拆分，但看着指數我想）

{1}{3}{2}{6}**{8}{7}** 

之後，它變成這樣：

{1,3}{2,6}**{7,8}**<<<<<<<< I am assuming we are using an if statement to arrange 
switching 7 and 8 in the merge process only takes O(n) 

然而，

我怎麼做這個的下傳的比較：

**{1,2,3,6}**{7,8} >>>> Wouldn't I need a nested for loop to compare and sort? 

在所有我看過exmaples，他們沒有解釋他們是如何管理來比較它，所有他們說是合併它，並顯示2個子陣列的圖片神奇地自我排序。我正在用C語言編寫這個代碼，我需要一些指導，以便在合併時如何獲得它。我想不出任何其他排序方式，但在合併後使用O（n^2）嵌套for循環。如果有人能告訴我如何做到這一點，那麼我將永遠快樂！

我想知道的是，如果我使用n^2算法排序，它不會是OlogN。

Answer 1

這裏是自下而上從Wikipedia's Merge Sort Implementation權合併：

BottomUpMerge(int A[], int iLeft, int iRight, int iEnd, int B[]) 
{ 
    int i0 = iLeft; 
    int i1 = iRight; 
    int j; 

    /* While there are elements in the left or right lists */ 
    for (j = iLeft; j < iEnd; j++) { 
     /* If left list head exists and is <= existing right list head */ 
     if (i0 < iRight && (i1 >= iEnd || A[i0] <= A[i1])) 
     { 
      B[j] = A[i0]; 
      i0 = i0 + 1; 
     } 
     else 
     { 
      B[j] = A[i1]; 
      i1 = i1 + 1; 
     } 
    } 
}