InsertionSort

template<class T>
void InsertionSort( T* arr, int n )
{
    for( int pass = 1; pass < n; ++pass )
    {
        int slot = pass;
        T val = arr[slot];
        while( slot > 0 && val < arr[slot - 1] )
        {
            arr[slot] = arr[slot - 1];
            --slot;
        }
        arr[slot] = val;
    }
}