merge_sort.cpp

template<typename T>                                                                                                                                       │
void merge(T begin, T end, T mid, T scratch_space){                                                                                                        │
                                                                                                                                                           │
    auto first{begin};                                                                                                                                     │
    auto second{mid};                                                                                                                                      │
    auto write{scratch_space};                                                                                                                             │
                                                                                                                                                           │
    // Alternate between subarrays to create sorted                                                                                                        │
    // sequence in the scratch space                                                                                                                       │
    for(int i{0};i<std::distance(begin,end);++i){                                                                                                          │
        if(first == mid){                                                                                                                                  │
            *write++ = *second++;                                                                                                                          │
        }                                                                                                                                                  │
        else if(second == end){                                                                                                                            │
            *write++ = *first++;                                                                                                                           │
        }                                                                                                                                                  │
        else{                                                                                                                                              │
            auto& source = (*first < *second) ? first : second;                                                                                            │
            *write++ = *source++;                                                                                                                          │
        }                                                                                                                                                  │
    }                                                                                                                                                      │
                                                                                                                                                           │
    // Copy the contents  of the scratch space back                                                                                                        │
    std::copy(scratch_space, write, begin);                                                                                                                │
}                                                                                                                                                          │
                                                                                                                                                           │
template<typename T>                                                                                                                                       │
void merge_sort(T begin, T end, T scratch_space){                                                                                                          │
                                                                                                                                                           │
    size_t length = std::distance(begin, end);                                                                                                             │
                                                                                                                                                           │
    if(length == 1){                                                                                                                                       │
        return;                                                                                                                                            │
    }                                                                                                                                                      │
                                                                                                                                                           │
    auto mid = begin+(length/2);                                                                                                                           │
    merge_sort(begin, mid, scratch_space);                                                                                                                 │
    merge_sort(mid, end, scratch_space);                                                                                                                   │
                                                                                                                                                           │
    merge(begin, end, mid, scratch_space);                                                                                                                 │
}