Sorting in alogorithm::sort

which sorting method is used in algorith::sort?? pleasse explain cause i am getting tle in quicksort and ac with this inbuilt sort.

you can have a look at this SO link!!!

sort is a function in C++ Standard Library that takes two random-access iterators, the start and the end, as arguments and performs a comparison sort on the range of elements between the two iterators, front-inclusive and end-exclusive. The specific sorting algorithm is not mandated and may vary across implementations. The GNU Standard C++ library, for example, uses a hybrid sorting algorithm: introsort is performed first, to a maximum depth given by 2×log2 n, where n is the number of elements, followed by an insertion sort on the result. Whatever the implementation, the complexity should be O(nlogn) comparisons on the average.

The two sorting algorithms, without optimizations enabled, should have comparable performance. The reason that the C++ sort tends to appreciably beat qsort is that the compiler can inline the comparisons being made, since the compiler has type information about what function is being used to perform the comparison

and worst compelxity of quick sort is O(n^2) . and complexity of std sort is always stable that is n*logn

2 Likes

The standard doesn’t require a particular algorithm, only that it must be stable, and that it complete the sort using approximately N lg N comparisons. That allows, for example, a merge-sort or a linked-list version of a quick sort (contrary to popular belief, quick sort isn’t necessarily unstable, even though the most common implementation for arrays is).

To be particular it will be mergesort in most cases.

u can find further discussion here :slight_smile: Discussion Link

2 Likes

@kpinturaj >> It uses a hybrid method, as @chandan11111 has mentioned. More details here, the wikipedia link.

//