c++ - 在 C++ 中使用迭代器进行合并排序

Question

我正在尝试使用 c++ 迭代器创建合并排序算法。我只想在不传入任何索引的情况下在整数 vector 上调用我的排序函数。

void MergeSort(std::vector<int> &vector)
{
    std::vector<int> numbers = vector;

    merge(numbers, vector, vector.begin(), vector.end());
}

是我的排序发起者，我的合并功能是:

void merge(std::vector<int> &vector, std::vector<int> &result, std::vector<int>::iterator start, std::vector<int>::iterator end)
{
    if ((end - start) < 2)
    {
        return;
    }

    if ((end - start) == 2)
    {
        if (*start > *(start + 1))
        {
            std::iter_swap(start, start + 1);
            return;
        }
    }

    std::vector<int>::iterator mid = result.begin() + result.size() / 2;
    merge(result, vector, vector.begin(), mid);
    merge(result, vector, mid, vector.end());

    std::vector<int>::iterator i = std::next(vector.begin(), start - result.begin());
    std::vector<int>::iterator j = std::next(vector.begin(), mid - result.begin());
    std::vector<int>::iterator idx = start;

    while (idx < end)
    {
        if (j >= end || (i < mid && *i < *j))
        {
            *idx = *i;
            i++;
        }
        else
        {
            *idx = *j;
            j++;
        }
        idx++;
    }
}

我的算法基于“简而言之的算法”一书。但是，在运行代码时出现段错误，这意味着我正在访问内存之外的值。
当我运行调试器时，我注意到我的 i 值有时是负数或非常大。

我相信我在这里对迭代器的使用是错误的，但是我不知道以什么方式。

Answer 1

问题就在这里

merge(result, vector, vector.begin(), mid);
merge(result, vector, mid, vector.end());

那应该是

merge(result, vector, start, mid);
merge(result, vector, mid, end);