dumb stuff

bigsort.cpp

// Puts work into a buffer so it can handle larger collections than the naive stack versions
template <class T>
struct QSWork {
    T* begins;
    T* ends;

    static QSWork Create( T* begins, T* ends ) {
        QSWork work;
        work.begins = begins;
        work.ends = ends;
        return work;
    }
};

template <class T>
void InPlace_Quicksort( const T* begins, const T* ends ) {
    std::stack<QSWork<T>> workStack;
    workStack.push( QSWork<T>::Create( begins, ends ) );
    while ( workStack.empty() == false ) {
        QSWork<T> work = workStack.top();
        workStack.pop();
        _InPlace_Quicksort(work, workStack);
    }
}

template <class T>
void _InPlace_Quicksort( const QSWork<T>& work, std::stack<QSWork<T>>& workStack ) {
    T* begins = work.begins;
    T* ends = work.ends;
    auto span = ends - begins;

    if ( span <= 0 )
        return;

    static const auto swap = []( auto* lhs, auto* rhs ) {
        auto t = *lhs;
        *lhs = *rhs;
        *rhs = t;
    };

    int* pivot = begins;

    for ( int* ptr = begins; ptr <= ends; ptr++ ) {
        if ( *ptr < *pivot ) {
            swap( ptr, pivot );
        }
    }

    workStack.push( QSWork<T>::Create(begins, pivot - 1) );
    workStack.push( QSWork<T>::Create(pivot + 1, ends) );
}

dumbsort.cpp

// This will SO on large spans

template <class T>
struct QSWork {
    T* begins;
    T* ends;

    static QSWork Create(T* begins, T* ends ) {
        QSWork work;
        work.begins = begins;
        work.ends = ends;
        return work;
    }
};

template <class T>
void InPlace_Quicksort( T* begins, T* ends ) {
    std::stack<QSWork<T>> workStack;
    workStack.push( QSWork<T>::Create( begins, ends ) );
    while ( workStack.empty() == false ) {
        QSWork<T> work = workStack.top();
        workStack.pop();
        _InPlace_Quicksort(work, workStack);
    }
}

template <class T>
void _InPlace_Quicksort( const QSWork<T>& work, std::stack<QSWork<T>>& workStack ) {
    T* begins = work.begins;
    T* ends = work.ends;
    auto span = ends - begins;

    if ( span <= 0 )
        return;

    static const auto swap = []( auto* lhs, auto* rhs ) {
        auto t = *lhs;
        *lhs = *rhs;
        *rhs = t;
    };

    int* pivot = begins;

    for ( int* ptr = begins; ptr <= ends; ptr++ ) {
        if ( *ptr < *pivot ) {
            swap( ptr, pivot );
        }
    }

    workStack.push( QSWork<T>::Create(begins, pivot - 1) );
    workStack.push( QSWork<T>::Create(pivot + 1, ends) );
}