Which one is faster, sort() or qsort()?

general
,
1

People who code in C use the built-in QSORT, while C++ users prefer the SORT function. Looking through the documentation, I see that both have an average time complexity of nlog(n). But [in GeekForGeeks][1] it says experimentally sort() was faster than qsort().

I was wondering why and how sort() is faster than qsort(), because its conventional that the same algorithm written in C would take up less memory and less time as well than the code in C++. And as far as I know both of these functions follow the same sorting algorithm. So isn’t qsort() supposed to take less time than sort()?

Is there any special reason/fact about these sorting function that makes C++'s sort() faster than C’s qsort()?
[1]: C qsort() vs C++ sort() - GeeksforGeeks

2
  • C++ sort has quick sort algorithm at its core.
  • Quicksort’s worst performance may be O(n^2). To avoid the worst case the recursion depth is recorded. If the recursion depth increase 2x log(n) then it falls back to Heap Sort.
  • Pivot selection strategies are also optimised. One of the most common optimisations is taking median of 3 random pivots
  • When the size of array decreases in the recursion tree, Insertion Sort is used. This is because insertion sort tends to be faster when number of elements are less and the array is almost sorted.

Reference taken from : Ashish kedia’s answer

1 Like
3

STL’s sort ran faster than C’s qsort, because C++’s templates generate optimized code for a particular data type and a particular comparison function.

Can you explain what this sentence is saying? How using different comparison functions for different data types helps to optimize the code?

4

So sort() uses some kinda dynamic sorting algorithm rather than just QuickSort?

5

Yes, it is a mixture of quicksort,Heap sort,insertion sort. It will pick the algorithm based on the data you are sorting.

6

Thanks, you referred me to another new term for me, Pivot Selection.