就地排序有2個排序子陣列的數組

Question

[這是一個面試問題。我找不到重複。]

一個數組包含兩個子排序數組。給出一個就地算法來排序兩個子數組。

爲例如：I/P：1 4 5 7 8 9 2 3 6 10 11 O/P：1 2 3 4 5 6 7 8 9 10 11

我在就地方面認爲合併排序，插入排序（因爲子數組已經排序）和快速排序的方面，但不能想到一個解決方案，它比使用標準排序方法提供了更好的複雜性。

請幫我找一個算法，它允許我們利用排序後的子數組屬性，並導致比在輸入上運行Quicksort更好的時間複雜度。

這是合併排序模擬我想，用這個例子：

1) For position 0, Comparing 1 & 2, 1 is smaller let it stay at it's original place 
    2) For position 1, Comparing 2 & 4, 2 is smaller so swap 2 and 4 
    3) For position 2, Comparison now is between 4 and 3 (5 > 4 anyways) swap 3 and 5 
    4) For position 3, Comparison between 4 & 5, swap 4 and 7 
    5) For position 4, Comparison between 7 & 5, swap 8 and 5 
    6) For position 5, Comparison between 7 & 8 (OUCH!!) it should have been between 7 & 6 

看來，這個問題類似於排序矩陣，其中就地合併過於複雜的排序行。

Answer 1

請參閱http://comjnl.oxfordjournals.org/content/38/8/681.full.pdf+html瞭解線性時間算法以解決此確切問題，並指出花費了多少努力來解決該問題。

我的猜測是面試官有一些他們認爲可以工作的可愛答案，這並不是真的。第二個最好的猜測是，他們沒有指定複雜性的原因。

在一次採訪中，我實際上會說：「我不知道如何有效地做到這一點，儘管我確信有關於這個問題的研究，但這是一個無效的答案。」然後，我會做一些明確的工作。

Answer 2

存在一個O（n log n）最壞情況行爲的就地合併排序，但正如論文所述，「由於涉及常數因素，算法主要是理論上的興趣。」請參閱https://stackoverflow.com/a/2571104/56778

如果您無法分配與其中一個排序子陣列一樣大的臨時緩衝區，就地合併非常困難。

Answer 3

對於面試問題，在您的算法中，一旦交換結果數組不再單獨排序了。您應該向較大的交換元素「冒泡」，直到它到達正確的位置，然後繼續。

讓我們爲了簡單起見採用2個數組，以topA和topB作爲當前位置（最初都是0）。讓所需的結果數組爲A [1..m] .. B [1..n]。這是一個僞代碼：

if (A[topA] < B[topB]) { 
    swap (A[topA], B[topB]) 
    index = topB; 
    while (B[index] < B[index + 1]) { 
     swap(B[index], B[index + 1]) 
    } 
    topB++ 
} else { 
    topA++; 
} 

在上面的每次運行結束時，結果數組排序和更小。這可以繼續，直到其中一個陣列用完。但由於冒泡階段的複雜性會比O（m + n）大。

Answer 4

// since both are sorted use array b as min heap 
    // if a[i] > b[0] (top of min-heap), exch it and heapify b 
    // order : O(nlog(n)) 
    void inplaceMerge(vector<int>& a, vector<int>& b) 
    { 
    for (int i=0; i < a.size(); i++) { 
     if (a[i] > b[0]) { 
       swap(a[i], b[0]); 
       sink(b, 0, b.size()-1); // bubbleDown() operation in heap() 
     } 
     } 
     sort(b.begin(), b.end()); 
    } 

    void sink(vector<int>& b, int i, int n) 
    { 
      int j = 2*i + 1; 
      while (j <= n) { 
       if (j+1 < n && b[j+1] < b[j]) j++; 
       if (b[j] < b[i]) swap(b[i], b[j]); 
       else break; 
       i = j; 
       j = 2*i + 1; 
      } 
    }