c++calgorithmsortingintrosort

Why std::sort is faster than "introsort" coded by hand?


I implemented introsort using quicksort, heapsort.. My hand coded version is based on D. Musser's suggestionn with the recursion depth to switch to heapsort passed as a parameter, median-of-3 pivot selection. The element threshold for switching to the simple insertion sort was 16.


Solution

  • Both gcc and Microsoft's VisualC++ provide source code for std::sort (in header file algorithm). So, you can take a look yourself. I have investigated similar issues before. My conclusion was that the code was optimized for the general code path even to the extent of making the code more complex and difficult to maintain. Trade-offs that make sense to me.