// Template functions for simple sort

#ifndef _SORT_H
#define _SORT_H

#include <iostream>
using namespace std;

// Swap two objects of the same type
template <class T>
void _swap(T & x, T & y) {
    T tmp = x; x = y; y = tmp;
}

// General sorting - interpolated from K&R
template <class T>
void _sort(T & vlist, int left, int right) {
    int last;
    if (left >= right)
        return;  // Nothing to do for fewer than two elements
    _swap(vlist[left], vlist[(left + right)/2]);
    last = left;
    for (int i = left + 1; i <= right; ++i)
        if (vlist[i] < vlist[left])
            _swap(vlist[++last], vlist[i]);
    _swap(vlist[left], vlist[last]);
    _sort(vlist, left, last - 1);
    _sort(vlist, last + 1, right);
}

template <class T>
void sort(T & vlist, int length) {
    _sort(vlist, 0, length - 1);
}

#endif