用指向數組的指針進行合併排序

Question

我正在嘗試使用stl庫進行合併排序算法，但遇到一些問題。下面是我使用

template <typename Item, typename SizeType> 
void merge_sort(Item array[], SizeType size){ 
    size_t n1; //Size of the first subarray 
    size_t n2; //Size of the second subarray 

    if(size > 1){ 
     //Compute the size of the subarrays 
     n1 = size/2; 
     n2 = size - n1; 

     //create the temp array. 
     int* n1Temp = new int[n1]; 
     int* n2Temp = new int[n2]; 
     int i; 
     for(i = 0; i < n1; i++) 
      n1Temp[i] = array[i]; 
     for(i = 0; i < n2; i++) 
      n2Temp[i] = array[i + n1]; 

     //recursive calls 
     merge_sort(n1Temp, n1);//sort from array[0] through array[n1 - 1] 
     merge_sort(n2Temp, n2);//sort from array[n1] to the end 

     //Merge the two sorted halves. 
     vector<int> v(array, array + size); 
     merge(n1Temp, n1Temp + n1, n2Temp, n2Temp + n2, v.begin());  
     copy(v.begin(), v.end(), array);//copy the vector back to the array 

     delete[] n1Temp; 
     delete[] n2Temp; 
    } 
} 

代碼排序不錯，但問題是，它就像一個澳碼（N^2）算法，而不是爲O（n \ log n）的，這是由於創作在每個合併排序調用中的矢量（我認爲）。我試圖消除載體，只是用在合併功能的陣列可以在下面

//Merge the two sorted halves. 
    int* finalArray = new int[n1 + n2]; 
    merge(n1Temp, n1Temp + n1, n2Temp, n2Temp + n2, begin(finalArray)); 
    array = finalArray; 

可以看出但這讓我不過是錯誤的。有什麼我能做的，以挽救我的合併排序算法？

Answer 1

正如Vaughn和user93353指出的那樣，您應該能夠在每個合併點直接合併到目標數組中。但是你仍然可以使用std :: vector <>來讓你自己更容易。另外，你的臨時數組是直接類型'int'的，我相當確定這是模板參數的類型Item。我不確定SizeType參數的用途，但是如果您有特別的想法，我將它留下。不管是什麼，它最好是兼容size_t：

template <typename Item, typename SizeType> 
void merge_sort(Item array[], SizeType size) 
{ 
    if(size > 1) 
    { 
     //Compute the size of the subarrays 
     size_t n1 = size/2; 

     //create the temp array 
     std::vector<Item> n1Temp(array, array+n1); 
     std::vector<Item> n2Temp(array+n1, array+size); 

     //recursive calls 
     merge_sort(&n1Temp[0], n1);  //sort array[0] through array[n1-1] 
     merge_sort(&n2Temp[0], size-n1); //sort array[n1] through array[size-1] 

     // merge the sorted halves 
     std::merge(n1Temp.begin(), n1Temp.end(), 
        n2Temp.begin(), n2Temp.end(), array); 
    } 
} 

上述技術拆分通過複製子序列自上而下，然後就地合併所述分裂複製到原始數組。您可以通過執行原來的陣列上的分裂，然後沒入臨時空間和複製後，我認爲你試圖在第一個這樣做的一個子表分配時間（但沒有更小的空間）減少這種算法地點：

template <typename Item> 
void merge_sort(Item ar[], size_t n) 
{ 
    if (n > 1) 
    { 
     // Compute the size of the subarrays 
     size_t n1 = n/2; 

     // invoke recursion on the submerges 
     merge_sort(ar, n1);  //sort array[0] through array[n1-1] 
     merge_sort(ar+n1, n-n1); //sort array[n1] through array[size-1] 

     // create merge-buffer 
     std::vector<Item> mrg; 
     std::merge(ar, ar+n1, ar+n1, ar+n, back_inserter(mrg)); 
     std::copy(mrg.begin(), mrg.end(), ar); 
    } 
} 

---

一般基於迭代器解決方案

對於一般的解決方案，允許更大的靈活性，您可以根據迭代器，而不是項目的指針定義合併排序。它變得有點多毛，但好處是非常簡單。

template <typename Iterator> 
void merge_sort(Iterator first, Iterator last) 
{ 
    typedef typename std::iterator_traits<Iterator>::value_type value_type; 
    typedef typename std::iterator_traits<Iterator>::difference_type difference_type; 

    difference_type n = std::distance(first, last)/2; 
    if (n == 0) 
     return; 

    // invoke recursion on the submerges 
    merge_sort(first, first + n); 
    merge_sort(first + n, last); 

    // create merge-buffer 
    std::vector<value_type> mrg(std::distance(first, last)); 
    std::merge(first, first+n, first+n, last, mrg.begin()); 
    std::copy(mrg.begin(), mrg.end(), first); 
} 

---

最後，如果發現自己排序一噸固定長度C-陣列你會發現下面的有益的（它使用上述一般迭代器溶液）：

// front-loader for C arrays 
template<typename Item, size_t N> 
void merge_sort(Item (&ar)[N]) 
{ 
    merge_sort(std::begin(ar), std::end(ar)); 
} 

它使下面的代碼相當方便：

int arr[1024]; 
... fill arr ... 
merge_sort(arr);