就地合併排序

Question

我有一點麻煩想出一個工作就地合併排序。有沒有人有任何算法或技巧可以幫助我開始？

Answer 1

mergesort.cpp

#include "mergesort.h" 
#include <limits> 
#include <vector> 
#include <iostream> 
using namespace std; 

void merge_sort(int *data, int start, int end){ 
    if (start < end){ 
     int middle = int((end + start)/2); 
     merge_sort(data, start, middle); 
     merge_sort(data, middle+1, end); 
     merge(data, start, middle+1, end); 
    } 
} 


void merge(int *data, int start, int middle, int end){ 
    int left[middle-start+1]; 
    for (int l_cnt=0; l_cnt<middle-start; l_cnt++){ 
     left[l_cnt] = data[start+l_cnt]; 
    } 
    left[middle-start] = numeric_limits<int>::max(); 
    int right[end-middle+2]; 
    for (int r_cnt=0; r_cnt<end-middle+1; r_cnt++){ 
     right[r_cnt] = data[middle+r_cnt]; 
    } 
    right[end-middle+1] = numeric_limits<int>::max(); 
    int i = 0; 
    int j = 0; 
    for (int k=start; k<=end; k++){ 
     if (left[i] < right[j]){ 
      data[k] = left[i]; 
      i++; 
     } 
     else{ 
      data[k] = right[j]; 
      j++; 
     } 
    } 
} 

mergesort.h

#ifndef INSERTIONSORT_H_ 
#define INSERTIONSORT_H_ 
void merge_sort(int *data, int start, int end); 
void merge(int *data, int start, int middle, int end); 
#endif 

和單元測試文件

#include "mergesort.h" 
#include "gtest/gtest.h" 

template<typename T, size_t size> 
    ::testing::AssertionResult ArraysMatch(const T (&expected)[size], 
              const T (&actual)[size]){ 
     for (size_t i(0); i < size; ++i){ 
      if (expected[i] != actual[i]){ 
       return ::testing::AssertionFailure() << "array[" << i 
        << "] (" << actual[i] << ") != expected[" << i 
        << "] (" << expected[i] << ")"; 
      } 
     } 
     return ::testing::AssertionSuccess(); 
} 

namespace{ 
    class MergeSortTest : public ::testing::Test{ 
     protected: 
      MergeSortTest() {} 
      virtual ~MergeSortTest() {} 
      virtual void SetUp() {} 
      virtual void TearDown() {} 
    }; 

    TEST(MergeSortTest, MergeTwo){ 
     int raw_array[] = {6,0,5,2,4,1,9,7}; 
     merge(raw_array, 2, 3, 3); 
     int sorted_array[] = {6,0,2,5,4,1,9,7}; 
     EXPECT_TRUE(ArraysMatch(sorted_array, raw_array)); 
    } 

    TEST(MergeSortTest, MergeFive){ 
     int raw_array[] = {6,0,2,5,1,4,9,7}; 
     merge(raw_array, 2, 4, 6); 
     int sorted_array[] = {6,0,1,2,4,5,9,7}; 
     EXPECT_TRUE(ArraysMatch(sorted_array, raw_array)); 
    } 

    TEST(MergeSortTest, SortTwo){ 
     int raw_array[] = {5, 2}; 
     int sorted_array[] = {2, 5}; 
     merge_sort(raw_array, 0, 1); 
     EXPECT_TRUE(ArraysMatch(sorted_array, raw_array)); 
    } 

    TEST(MergeSortTest, SortThree){ 
     int raw_array[] = {5, 2, 4}; 
     int sorted_array[] = {2, 4, 5}; 
     merge_sort(raw_array, 0, 2); 
     EXPECT_TRUE(ArraysMatch(sorted_array, raw_array)); 
    } 

    TEST(MergeSortTest, Five){ 
     int raw_array[] = {5, 2, 4, 1, 9}; 
     int sorted_array[] = {1, 2, 4, 5, 9}; 
     merge_sort(raw_array, 0, 4); 
     EXPECT_TRUE(ArraysMatch(sorted_array, raw_array)); 
    } 
} 

int main(int argc, char **argv){ 
    ::testing::InitGoogleTest(&argc, argv); 
    return RUN_ALL_TESTS(); 
} 

Answer 2

就地歸併即將與限制大小的緩衝區做歸併。並且它最終將如何合併兩個排序列表與小於結果的緩衝區。

STL具有in-place mergesort的實現。