base_sort.hh Source File

00001 /*
00008  * LEGAL:   COPYRIGHT (C) 2006 JIM E. BROOKS
00009  *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
00010  *          OF THE GNU GENERAL PUBLIC LICENSE VERSION 2 (GPL 2).
00011  *****************************************************************************/
00012 
00013 #ifndef BASE_SORT_HH
00014 #define BASE_SORT_HH 1
00015 
00016 #include "base_common.hh"
00017 
00018 namespace base {
00019 
00024 template<typename CONTAINER>
00025 void
00026 InsertionSort( CONTAINER& cont )
00027 {
00028     const int size = int(cont.size());
00029     if ( UX( size <= 1 ) )  // heaps with 0 or 1 elements are inherently sorted
00030         return;
00031 
00032     for ( int i = 1; i < size; ++i )
00033     {
00034         // Shortcut for heaps that are completely/almost sorted.
00035         if ( EX( cont[i-1] < cont[i] ) )
00036             continue;
00037 
00038         typename CONTAINER::value_type item = cont[i];
00039         int j;  // signed necessary
00040         for ( j = i-1; j >= 0 && item < cont[j]; --j )
00041         {
00042             cont[j+1] = cont[j];
00043         }
00044         cont[j+1] = item;
00045     }
00046 }
00047 
00048 } // namespace base
00049 
00050 #endif // BASE_SORT_HH