#ifndef MINMAX_SORT_H
#define MINMAX_SORT_H

#include <algorithm>
    
template <class RandomAccessIterator>
void minmax_sort(RandomAccessIterator first, RandomAccessIterator last)
{
    RandomAccessIterator begin = first;
    RandomAccessIterator end = last - 1;
    while (begin < end) {
        RandomAccessIterator it, min, max;
        bool started = false;
        for (it = begin; it <= end; ++it) {
            if (!started) {
                min = it;
                max = it;
                started = true;
            }
            else {
                if (*it < *min) {
                    min = it;
                }
                else if (*it > *max) {
                    max = it;
                }
            }
        }
        if (max == begin && min == end) {
            // Swap min and max only
            std::swap(*max, *min);
        }
        else if (max == begin) {
            // Swap max and end first
            std::swap(*max, *end);
            std::swap(*min, *begin);
        }
        else {
            // Swap min and begin first
            std::swap(*min, *begin);
            std::swap(*max, *end);
        }
        ++begin;
        --end;
    }
}

#endif // MINMAX_SORT_H