В этом разделе находятся сортировки, которые требуют минимальное количество сравнений, как в среднем, так и в наихудшем случае. В первом варианте они они сделаны в виде шаблонов функций для упорядочивания заданных элементов по возрастанию и убыванию:

//*********************** 14.12.2005 **************************//
//
//                 Сортировка двух элементов 
//      Сравнения: 1 в худшем случае, 1 в среднем
//
//*********************** 14.12.2005 **************************//

template <class T> inline void sort123 ( T & a0, T & a1 )...
template <class T> inline void sort321 ( T & a0, T & a1 )...


//*********************** 14.12.2005 **************************//
//
//                 Сортировка трёх элементов
//      Сравнения: 3 в худшем случае, 2.667 в среднем
//
//*********************** 14.12.2005 **************************//

template <class T> inline void sort123 ( T & a0, T & a1, T & a2 )...
template <class T> inline void sort321 ( T & a0, T & a1, T & a2 )...


//*********************** 14.12.2005 **************************//
//
//                 Сортировка 4-х элементов
//      Сравнения: 5 в худшем случае, 4.778 в среднем
//
//*********************** 14.12.2005 **************************//

template <class T> inline void sort123 ( T & a0, T & a1, T & a2, T & a3 )...
template <class T> inline void sort321 ( T & a0, T & a1, T & a2, T & a3 )...


//*********************** 15.12.2005 **************************//
//
//                 Сортировка пяти элементов
//      Сравнения: 7 в худшем случае, 6.933 в среднем
//
//*********************** 15.12.2005 **************************//

template <class T> inline void sort123 ( T & a0, T & a1, T & a2, T & a3, T & a4 )...
template <class T> inline void sort321 ( T & a0, T & a1, T & a2, T & a3, T & a4 )...


//*********************** 16.12.2005 **************************//
//
//                 Сортировка шести элементов
//      Сравнения: 10 в худшем случае, 9.578 в среднем
//
//*********************** 19.12.2005 **************************//

template <class T> inline void sort123 ( T & a0, T & a1, T & a2, T & a3, T & a4, T & a5 )...
template <class T> inline void sort321 ( T & a0, T & a1, T & a2, T & a3, T & a4, T & a5 )...

Во втором варианте шаблоны функций сортируют массивы:

template <class T> inline void sort2_123 ( T * a )...
template <class T> inline void sort2_321 ( T * a )...

template <class T> inline void sort3_123 ( T * a )...
template <class T> inline void sort3_321 ( T * a )...

template <class T> inline void sort4_123 ( T * a )...
template <class T> inline void sort4_321 ( T * a )...

template <class T> inline void sort5_123 ( T * a )...
template <class T> inline void sort5_321 ( T * a )...

template <class T> inline void sort6_123 ( T * a )...
template <class T> inline void sort6_321 ( T * a )...

Описание алгоритмов для пяти и шести элементов можно прочитать в книге "Искусство программирования" 3-й том раздел 5.3.1.

Исходники находятся в файле sorting.h.