Sort Containers with std::sort()

The problem of how to efficiently sort comparable elements is essentially solved. For most applications, there's no reason to re-invent this wheel. The STL provides an excellent sorting solution via the std::sort() algorithm. While the standard does not specify a sorting algorithm, it does specify a worst-case complexity of$O (nlogn)$, when applied to a range of n elements.

Just a few decades ago, the quicksort algorithm was considered a good compromise for most uses and was generally faster than other comparable algorithms. Today we have hybrid algorithmsHybrid algorithms refer to computational techniques that combine multiple approaches or methods, often combining the strengths of different algorithms, to achieve improved performance or solve complex problems more effectively. that choose between different approaches according to the circumstances, often switching algorithms on the fly. Most current C++ libraries use a hybrid approach with some combination of introsort and an insertion sort. std::sort() provides exceptional performance under most common circumstances.

How to do it

In this recipe, we'll examine the std::sort() algorithm. The sort() algorithm works with any container with random-access iterators. Here, we will use a vector of int:

• We'll start with a function to test if a container is sorted: