我的并归排序为什么不对

Question

能运行但排的不对，compare应该没问题

#include<iostream>
#include<vector>
using namespace std;

template<typename T, typename C>
void merge(typename vector<T>::iterator left, typename vector<T>::iterator mid,
    typename vector<T>::iterator end, C Compare, vector<T>&temp);

template<typename T,typename C>
void mergeSort(typename vector<T>::iterator begin, typename vector<T>::iterator end,C Compare,vector<T>&temp)
{
    if (begin < end)
    {
        auto mid = begin + distance(begin, end) / 2;
        mergeSort<T,C>(begin, mid, Compare,temp);
        mergeSort<T,C>(mid+1, end, Compare,temp);
        merge<T,C>(begin, mid, end, Compare, temp);
    }
    
}

template<typename T, typename C>
void merge(typename vector<T>::iterator left, typename vector<T>::iterator mid, 
    typename vector<T>::iterator right,C Compare, vector<T>&temp)
{
    auto i = left;
    auto j = mid+1;
    auto k = temp.begin();
    while (i !=mid && j != right)
    {
        if (Compare(i, j))
        {
            *k++ = *i++;
        }
        else
        {
            *k++ = *j++;
        }
    }
    while (i <=mid) *k++ = *i++;
    while (j <right) *k++ = *j++;

    move(temp.begin() , k , left);

    for (const auto it : temp)
    {
        cout << it << " ";
    }
    cout << endl;
}

struct Compare
{
    template<typename T>
    bool operator()(const T& a,const T& b) const
    {
        return *a < *b;
    }
};

int main()
{
    vector<int>vec = { 1,4,5,3,2 };
    vector<int>temp(vec.size());
    mergeSort<int,Compare>(vec.begin(), vec.end(), Compare{}, temp);
    for (const auto it : vec)
    {
        cout << it <<" ";
    }
    return 0;
}

Answer 1

#include <iostream>
#include <vector>
#include <iterator>
using namespace std;

template <typename T, typename C>
void merge(typename vector<T>::iterator left, typename vector<T>::iterator mid,
           typename vector<T>::iterator right, C Compare, vector<T> &temp);

template <typename T, typename C>
void mergeSort(typename vector<T>::iterator begin, typename vector<T>::iterator end, C Compare, vector<T> &temp)
{
    if (distance(begin, end) > 1)
    {
        auto mid = begin + distance(begin, end) / 2;
        mergeSort<T, C>(begin, mid, Compare, temp);
        mergeSort<T, C>(mid, end, Compare, temp);
        merge<T, C>(begin, mid, end, Compare, temp);
        
        // 打印排序过程
        for (auto it = begin; it != end; ++it)
        {
            cout << *it << " ";
        }
        cout << endl;
    }
}

template <typename T, typename C>
void merge(typename vector<T>::iterator left, typename vector<T>::iterator mid,
           typename vector<T>::iterator right, C Compare, vector<T> &temp)
{
    auto i = left;
    auto j = mid;
    auto k = temp.begin();

    while (i != mid && j != right)
    {
        if (Compare(*i, *j))
        {
            *k++ = *i++;
        }
        else
        {
            *k++ = *j++;
        }
    }
    while (i != mid)
        *k++ = *i++;
    while (j != right)
        *k++ = *j++;

    move(temp.begin(), k, left);
}

struct Compare
{
    template <typename T>
    bool operator()(const T &a, const T &b) const
    {
        return a < b;
    }
};

int main()
{
    vector<int> vec = {1, 4, 5, 3, 2};
    vector<int> temp(vec.size());
    mergeSort<int, Compare>(vec.begin(), vec.end(), Compare{}, temp);
    cout << "最终排序结果: ";
    for (const auto &it : vec)
    {
        cout << it << " ";
    }
    return 0;
}