/*****************************************************************************
 * $Id: gfx_sort.hh,v 1.1 2006/10/31 04:19:29 devel Exp $
 * @file
 * @author  Jim E. Brooks  http://www.jimbrooks.org
 * @brief   Sorting algorithms.
 *//*
 * LEGAL:   COPYRIGHT (C) 2006 JIM E. BROOKS
 *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
 *          OF THE GNU GENERAL PUBLIC LICENSE (GPL).
 *****************************************************************************/

#ifndef GFX_SORT_HH
#define GFX_SORT_HH 1

namespace gfx {

/*****************************************************************************
 * Insertion sort for STL container (vector or deque).
 * Insertion sort is optimal for "almost sorted" or "completely sorted" heaps.
 *****************************************************************************/
template<typename CONTAINER>
void
InsertionSort( CONTAINER& cont )
{
    const int size = (int)cont.size();
    if ( size <= 1 )  // heaps with 0 or 1 elements are inherently sorted
        return;

    for ( int i = 1; i < size; ++i )
    {
        // Shortcut for heaps that are completely/almost sorted.
        if ( EX( cont[i-1] < cont[i] ) )
            continue;

        typename CONTAINER::value_type item = cont[i];
        int j;
        for ( j = i-1; j >= 0 && item < cont[j]; --j )
        {
            cont[j+1] = cont[j];
        }
        cont[j+1] = item;
    }
}

} // namespace gfx

#endif // GFX_SORT_HH
