Mergesort：修訂

Question

是否合併排序工作;

取值

分裂它的在兩個

採取每個列表的第一個元素列表，所述最低值的一箇中，以一個新的列表去（和我想從原始移除）。讓下面兩個數字共同出現 - 直到一個列表爲空，然後將另一個列表的剩餘部分放在nw列表的末尾？

另外，在鏈接列表上做這件事情的後果是什麼？

感謝

Answer 1

你描述的合併只（不排序）什麼，排序是在歸併排序recursivly完成。

Also, what are the ramifications of doing this on a linked list? 

這probalby太貴分裂鏈表，如果你有兩個有序列表，你可以很容易地將它們合併維持秩序。

Answer 2

合併排序的工作原理是將數組分成兩部分，然後在每部分中調用合併排序。當僅用一個元素調用合併排序時，它只是返回它。合併發生在遞歸之後，並按排序順序將數組重新排列在一起。

array mergesort(array) 
{ 
    if(array.len == 1) return array; 

    array temp1 = mergesort(array.firsthalf); 
    array temp2 = mergesort(array.secondhalf); 

    return merge(temp1, temp2); 
} 

將合併排序應用到鏈接列表的問題是你沒有簡單的方法將它分成兩半。你必須迭代，直到你到達中途。這會消耗額外的時間，並會不適當地影響合併排序的性能。 使用數組，您可以執行簡單的常量時間整數運算，將其分成兩部分。