爲什麼標準合併排序不到位？

Question

在合併排序的合併算法中，我不明白我們必須使用輔助數組L，R？爲什麼我們不能只保留2個指針來對應我們在2個子數組L和R中比較哪個元素，以便合併排序算法保持原位？

謝謝。

Answer 1

說你拆分你的數組s.th. L使用原始數組的前半部分，而R使用後半部分。

然後說durign合併來自R的頭幾個元素小於L中的最小值。如果你想把它們放在合併結果的正確位置，你將不得不覆蓋L中沒有被在合併步驟中處理。

當然你可以做出不同的分割。但是你總是可以構建這樣一個（然後稍微不同）的例子。