歸併排序變化

Question

要求通過合併排序4個陣列A，B，C和D的這些技術中的任何一個被允許：

1. 應用4路合併。
2. 合併A和B.將C與前一個合併的輸出合併。最後將D與最後一個輸出合併。
3. 將A與B和C合併爲D.現在合併兩個輸出。

在比較和轉移方面，每種技術的優點和缺點是什麼？

Answer 1

有兩種效率方法可以在這裏考慮：

a。內存使用情況。

灣性能。

第一種技術具有低內存使用率，因爲它不產生中間數組。

第三種技術具有很高的性能，因爲A/B和C/D可以並行合併，然後合併中間數組。

最後，第二種技術既沒有上述特徵。