合併具有恆定存儲器的陣列的兩個排序部件在O（n）的時間

Question

假設我們有長度的數組ñ其中來自子陣列至N/2和N/2至N元素排序。是否可以使用O（N）時間內的常量內存對整個陣列進行排序？數組的

例子：

10, 20, 30, 40, 1, 2, 35, 60 

Answer 1

你要到位合併。見this和this。此外，搜索谷歌「就地合併」會給你很多好的結果。這些算法在實踐中並不容易實施，所以通常沒有人會因此而煩惱。