Big-O Notation describes the limiting behavior when n is large, also known as asymptotic behavior. This is an approximation. (See http://en.wikipedia.org/wiki/Big_O_notation) Insertion sort is faster for small n because Quick Sort has extra overhead from the recursive function calls. Insertion sort is also more stable than Quick sort and requires less memory. This question describes … Read more
The simple answer to the question: template< typename T > typename std::vector<T>::iterator insert_sorted( std::vector<T> & vec, T const& item ) { return vec.insert ( std::upper_bound( vec.begin(), vec.end(), item ), item ); } Version with a predicate. template< typename T, typename Pred > typename std::vector<T>::iterator insert_sorted( std::vector<T> & vec, T const& item, Pred pred ) { … Read more
Selection Sort: Given a list, take the current element and exchange it with the smallest element on the right hand side of the current element. Insertion Sort: Given a list, take the current element and insert it at the appropriate position of the list, adjusting the list every time you insert. It is similar to … Read more
(Following up on the suggestion of @HelloWorld to look into sorting networks.) It seems that a 29-comparison/swap network is the fastest way to do a 10-input sort. I used the network discovered by Waksman in 1969 for this example in JavaScript, which should translate directly into C, as it’s just a list of if statements, … Read more