使用迭代器的C++合并排序

Question

目前，我正在尝试创建一个简单的C++合并排序程序。

using namespace std;
using Iterator = std::vector<int>::iterator;
using CIterator = std::vector<int>::const_iterator;
std::vector<int> merge(CIterator left_begin, CIterator left_end, CIterator right_begin, CIterator right_end) {
std::vector<int> result;

CIterator left = left_begin;
CIterator right = right_begin;

while (left != left_end && right != right_end) {
if (*left <= *right) {
result.push_back(*left);
left++;
} else {
result.push_back(*right);
right++;
}
}

while (left != left_end) {
result.push_back(*left);
left++;
}

while (right != right_end) {
result.push_back(*right);
right++;
}

return result;
}

我创建了一个merge函数，它基本上将两个排序的向量连接为一个向量并返回它(我将使用下面的函数merge的返回类型(。然后尝试编写驱动程序函数合并排序我有以下代码，我认为它正确工作

void merge_sort(Iterator begin, Iterator end) {
auto difference = distance(begin, end);

if (difference <= 1) {
return;
}

Iterator middle = begin;
advance(middle, difference / 2);

merge_sort(begin, middle);
merge_sort(middle, end);

vector<int> result = merge(begin, middle, middle, end);
// But what to put here?
}

在注释标记的位置，我不明白该写什么才能在递归中使排序数组更上一层楼。我试过

begin = result.begin();
end = result.end();

但是显然不起作用

Answer 1

问题是merge_sort的类型签名假设了一个就地算法：

void merge_sort(Iterator begin, Iterator end);

但是merge过程没有到位，而是返回数组的合并副本。您需要更改merge以保持原位，或者需要更改merge_sort以返回排序后的数组。后一种解决方案(更简单但效率较低(如下：

std::vector<int> merge_sort(Iterator begin, Iterator end) {
auto difference = distance(begin, end);

if (difference <= 1) {
return;
}

Iterator middle = begin;
advance(middle, difference / 2);

std::vector<int> left = merge_sort(begin, middle);
std::vector<int> right = merge_sort(middle, end);
return merge(left.begin(), left.end(), right.begin(), right.end());
}

Answer 2

一种优化的自上而下的合并排序，对第二个向量进行一次分配，然后使用一对相互递归的函数(…AtoA，…AtoB(根据递归级别交替合并方向。(我省略了原型(。

void MergeSort(     typename std::vector<int>::iterator &ab,
typename std::vector<int>::iterator &ae)
{
size_t sz = ae - ab;
if (sz < 2)
return;
std::vector<int> vb(sz);           // temp vector
std::vector<int>::iterator bb = vb.begin();
std::vector<int>::iterator be = vb.end();
MergeSortAtoA(ab, ae, bb, be);
}
void MergeSortAtoA( typename std::vector<int>::iterator &ab,
typename std::vector<int>::iterator &ae,
typename std::vector<int>::iterator &bb,
typename std::vector<int>::iterator &be)
{
size_t sz = ae - ab;
if(sz < 2)                              // if 1 element return
return;
std::vector<int>::iterator am = ab+(sz/2);
std::vector<int>::iterator bm = bb+(sz/2);
MergeSortAtoB(ab, am, bb, bm);
MergeSortAtoB(am, ae, bm, be);
Merge(bb, bm, be, ab);
}
void MergeSortAtoB( typename std::vector<int>::iterator &ab,
typename std::vector<int>::iterator &ae,
typename std::vector<int>::iterator &bb,
typename std::vector<int>::iterator &be)
{
size_t sz = ae - ab;
if(sz < 2){                             // if 1 element, copy it
*bb = *ab;
return;
}
std::vector<int>::iterator am = ab+(sz/2);
std::vector<int>::iterator bm = bb+(sz/2);
MergeSortAtoA(ab, am, bb, bm);
MergeSortAtoA(am, ae, bm, be);
Merge(ab, am, ae, bb);
}
void Merge(         typename std::vector<int>::iterator &ab,
typename std::vector<int>::iterator &am,
typename std::vector<int>::iterator &ae,
typename std::vector<int>::iterator &bb)
{
std::vector<int>::iterator mb = ab;    // left  run iterator
std::vector<int>::iterator mm = am;    // right run iterator
std::vector<int>::iterator bi = bb;    // merge run iterator
while(1){                               // merge data
if(*mb <= *mm){                     // if mb <= mm
*bi++ = *mb++;                  //   copy mb
if(mb < am)                     //   if not end left run
continue;                   //     continue (back to while)
while(mm < ae)                  //   else copy rest of right run
*bi++ = *mm++;
break;                          //     and return
} else {                            // else mb > mm
*bi++ = *mm++;                  //   copy mm
if(mm < ae)                     //   if not end of right run
continue;                   //     continue (back to while)
while(mb < am)                  //   else copy rest of left run
*bi++ = *mb++;
break;                          //     and return
}
}
}