就地合并排序

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

和unittest文件

#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

In-place mergesort是关于使用有限大小的缓冲区进行mergesort。最后是如何用比结果更小的缓冲区来合并两个排序的列表。

STL实现了就地合并排序。