qsort_arrayはQuickSortアルゴリズムの実装です。operator []インターフェースのような配列を持つものはすべてソートされます。クイックソートが不安定になると、ヒープソートに切り替わります。このように、ソートは最大でN * log(N)時間かかることが保証されています。 

#include <dlib / sort.h>

    template <
        typename T,
        typename compare
    inline void qsort_array (
        T& array,
        unsigned long left,
        unsigned long right,
        const compare& comp 
            - T implements operator[]                                 
            - the items in array must be comparable by comp where comp is a function
              object with the same syntax as std::less<>
            - the items in array must be swappable by a global swap()   
            - left and right are within the bounds of array
              i.e. array[left] and array[right] are valid elements
            - left <= right
            - for all elements in #array between and including left and right the 
              ith element is < the i+1 element
            - sorts using a quick sort algorithm

Posted by kinya