Mergesort

#ifndef RANGE_H_EMS
#define RANGE_H_EMS

#include <vector>

namespace MergeSort_EMS
{
    template <typename T>
    class Range
    {
    public:
        Range( T* begin, unsigned elements ) : _array(begin), _nElements(elements)
        {
        }

        unsigned size() const { return _nElements ; }
        operator T*() { return _array; }

    private:

        T* _array ;
        unsigned _nElements ;
    };


    // ranges fed to merge are expected to be contiguous memory where
    // a would house the earlier of the indexes in an array that composed
    // the two.
    template <typename T>
    Range<T> merge( Range<T> a, Range<T> b, std::vector<T>& scratch )
    {
        scratch.clear() ;

        Range<T> merged( a, a.size()+b.size() ) ;

        unsigned aIdx = 0 ;
        unsigned bIdx = 0 ;
        unsigned processed = 0 ;

        // members of a that are not greater than b[0] will not need to be moved.
        while ( aIdx < a.size() && a[aIdx] <= b[bIdx] )
            ++aIdx, ++processed ;

        // once we reach an element in a that is greater than b[0], the rest
        // of the elements in a must be moved to scratch.
        if ( aIdx < a.size() )
        {
            scratch.insert(scratch.begin(), a+aIdx, a+a.size() ) ;
            unsigned sIdx = 0 ;

            while ( processed < merged.size() && sIdx < scratch.size() && bIdx < b.size() )
            {
                if ( scratch[sIdx] <= b[bIdx] )
                    merged[processed] = scratch[sIdx++] ;
                else
                    merged[processed] = b[bIdx++] ;
                ++processed ;
            }

            if ( processed == merged.size() )
                return merged ;

            if ( bIdx == b.size() )
            {  // only stuff in scratch left
                while ( processed < merged.size() )
                    merged[processed++] = scratch[sIdx++] ;
            }
        }

        // at this point, anything left in b should already be in the correct position.
        return merged ;
    }
}
#endif

#ifndef MERGESORT_H_EMS
#define MERGESORT_H_EMS

#include <algorithm>
#include <vector>


namespace MergeSort_EMS
{
    template <typename T>
    void twosies(T* array, unsigned size)
    {
        unsigned max_iterations = size / 2 ;

        for ( unsigned i=0; i < max_iterations; ++i )
        {
            if ( *array > *(array+1) )
                std::swap( *array, *(array+1) ) ;

            array += 2 ;
        }
    }

    template <typename T>
    void merge_sort(std::vector<T> & sortee)
    {
        // prepare our two-element sorted subarrays
        // reduces the maximum number of ranges we need to store
        // at one time by half.
        twosies(sortee.data(), sortee.size()) ;

        // memory buffer to feed to merge
        std::vector<T> scratch ;
        scratch.reserve((sortee.size()+1)/2) ;

        std::vector<Range<T>> ranges ;
        ranges.reserve((sortee.size()+1)/2) ;

        // generate initial twosie Ranges
        {
            const unsigned num_twosies = sortee.size() / 2 ;
            T* ptr = sortee.data() ;
            for ( unsigned i=0;  i<num_twosies;  ++i )
            {
                ranges.push_back(Range<T>(ptr, 2));
                ptr += 2;
            }

            if ( sortee.size() % 2 )
                ranges.push_back(Range<T>(ptr, 1)) ;
        }

        // work the merge
        while ( ranges.size() > 1 )
        {
            unsigned max_to_merge = ranges.size() - ranges.size()%2 ;

            unsigned i ;
            for ( i=0;  i<max_to_merge; i+=2 )
            {
                Range<T> r1 = ranges[i] ;
                Range<T> r2 = ranges[i+1] ;

                // CAUTION:  See merge definition/comments before changing what is fed to it.
                ranges[i/2] = merge(r1, r2, scratch) ;
            }

            if ( ranges.size()%2 )    // odd man out
                ranges[i/2] = ranges.back() ;

            // Use of resize requires a default constructor if used with only one argument,
            // Range doesn't have a default constructor and we don't need one.   Feed resize
            // a bullshit argument so we don't have to implement a default constructor.  Since
            // we're only reducing the size of the vector, it won't be used anyway.
            ranges.resize(max_to_merge/2 + ranges.size()%2, Range<T>(0,0)) ;
        }
    }
};
#endif

#ifndef TOSORT_H_EMS
#define TOSORT_H_EMS

#include <vector>
#include <limits>
#include <functional>

const unsigned nullindex = std::numeric_limits<unsigned>::max() ;

class ToSort
{
public:
    static std::function<void(unsigned,unsigned, unsigned)> update_func ;

    ToSort(const std::vector<ToSort>& v, unsigned id) ;
    ToSort(const ToSort & c);
    ToSort(ToSort && c) ;

    ToSort& operator=(ToSort&&c) ;
    ToSort& operator=(const ToSort& c) ;

    operator unsigned() const { return _id ; }

private:

    const std::vector<ToSort>* _container ;
    unsigned _id ;
    unsigned _prev_pos ;


    void _update_notify() const ;
    bool _in_container() const ;
    unsigned _container_pos() const ;
};
#endif

#include <vector>
#include <limits>

 std::function<void(unsigned,unsigned, unsigned)> ToSort::update_func = nullptr ;

 ToSort::ToSort(const std::vector<ToSort>& v, unsigned id)
     : _container(&v), _id(id), _prev_pos(nullindex)
 {
 }

 ToSort::ToSort(const ToSort& c)
     : _container(c._container), _id(c._id), _prev_pos(c._container_pos())
 {
    _update_notify() ;
 }

 ToSort::ToSort(ToSort&& c)
     : _container(c._container), _id(c._id), _prev_pos(c._container_pos())
 {
     _update_notify() ;
 }

 ToSort& ToSort::operator=(ToSort&&c)
 {
     *this = c ;
     c._container = nullptr ;
     return *this ;
 }

 ToSort& ToSort::operator=(const ToSort& c)
 {
     _container = c._container ;
     _id = c._id ;
     _prev_pos = c._container_pos() ;
     _update_notify() ;
     return *this ;
 }

 void ToSort::_update_notify() const
 {
     if ( update_func != nullptr && _container != nullptr )
         update_func(_container_pos(), _id, _prev_pos) ;
 }

 // if we append or push a ToSort to the end of a container,
 // _in_container() may be called before the container has updated
 // its size to reflect the addition, so of this is one past the end
 // of the container we will consider it to be in the container.
 bool ToSort::_in_container() const
 {
     if ( _container == nullptr )
         return false ;

    ToSort const * array = _container->data() ;

    if ( this >= array && array + _container->size() >= this )
        return true ;

    return false ;
 }

unsigned ToSort::_container_pos() const
{
    if ( _in_container() )
        return this - _container->data() ;
    else
        return nullindex ;
}

#include <numeric>
#include <iostream>
#include <vector>
#include <random>

namespace ms = MergeSort_EMS ;

void populate_vector(std::vector<ToSort>& v)
{
    v.clear() ;

    std::random_device rd ;

    const unsigned v_size = rd() % 15 + 6 ;

    for ( unsigned i=0;  i<v_size;  ++i )
        v.push_back(ToSort(v, i)) ;

    std::shuffle(v.begin(), v.end(), rd ) ;
}

class OnUpdate
{
    std::vector<ToSort>& _v ;
public:

    OnUpdate(std::vector<ToSort>& v) : _v(v) {}

    void operator()(unsigned index, unsigned id, unsigned prev_index)
    {
        if ( prev_index == nullindex )
            std::cout << id << " was inserted  at " << index << '\n' ;
        else
        {
            if ( index == nullindex )
                std::cout << id << " was removed from " << prev_index << '\n' ;
            else
                std::cout << id << " was moved from " << prev_index << " to " << index << '\n' ;
        }
    }
};

void show(const std::vector<ToSort>& v)
{
    std::cout << "{ " ;
    for ( unsigned i=0; i< v.size();  ++i )
    {
        std::cout << v[i] << ' ' ;
    }
    std::cout << "}\n" ;
}

int main()
{
    std::vector<ToSort> v ;
    v.reserve(100) ;
    OnUpdate update(v) ;
    ToSort::update_func = update ;

    do
    {
        ToSort::update_func = nullptr ;   // disable updating while populating the vector
        populate_vector(v) ;
        ToSort::update_func = update ;

        show(v) ;
        ms::merge_sort(v) ;
        show(v) ;

        std::cout << '\n' ;

    } while ( std::cin.get() == '\n' ) ;
}