Merge Sort (C++)

merge_sort.h

template <class FwdIt>
FwdIt Merge(
    FwdIt first1, FwdIt last1,
    FwdIt first2, FwdIt last2,
    FwdIt result
    )
{
    while (true)
    {
        if (*first2 < *first1)
        {
            *result++ = *first2++;
        }
        else
        {
            *result++ = *first1++;
        }
        
        if (first1 == last1)
            return copy(first2, last2, result);
        
        if (first2 == last2)
            return copy(first1, last1, result);
    }
}

template <typename FwdIt>
void MergeSort(FwdIt beg, FwdIt end)
{
    std::size_t size = std::distance(beg, end);
    typedef typename std::iterator_traits<FwdIt>::value_type T;

    if (size > 1)
    {
        // Find the mid-point of the array
        FwdIt mid = beg;
        std::advance(mid, size / 2);
    
        // Sort the first half
        MergeSort(beg, mid);
    
        // Sort the last half
        MergeSort(mid, end);

        std::vector<T> buf(size);
    
        Merge(beg, mid, mid, end, buf.begin());

        std::copy(buf.begin(), buf.end(), beg);
    }
    else
    {
        // A 1-length array is already sorted
        return;
    }
}