Sorting is one of the most fundamental operations in computer science. It helps you organise your data. Search times can be drastically reduced by using sorted data, be it numbers, text, or even domain-specific objects. In C++, the Standard Template Library (STL) offers an extremely versatile and high-performance function for sorting, known as sort(). The STL library is designed to be user-friendly, with preset functions and data structures. Additionally, algorithms, iterators, and container classes are part of STL in C++.
In this article, we will deep dive into the sort() function in C++, how it works, its types, different ways to use it, and various applications in real life. We would also look at comparators, lambdas, and function objects for custom sorting techniques.
What is Sorting?
Sorting is the process of arranging the elements in some specific order (ascending or descending) concerning a criterion. Sorting is performed everywhere, whether it is mathematics, counting of numbers, etc. In almost every application, sorting is a fundamental operation – be it sorting the records of a database, or adjusting how products are listed on an e-commerce site.
The sort() Function in C++
The C++ Standard Template Library (STL) provides several algorithms to make sorting fast and simple. The std::sort() is a built-in function in the C++ programming language that is used to arrange data structures of any kind in the desired sequence. It is defined In the <algorithm> header file. This function can sort arrays, vectors, and other data structures based on either a default comparison operator or a custom-defined comparator. The given below is the syntax for defining the sort() function in C++:
Syntax:
std::sort(first, last, comp);
In the C++ STL, the sort() function is the preferred sorting tool. In practice, it employs a very effective quicksort algorithm, but depending on the circumstance, it may also use introsort or heapsort.
Parameters of sort() function
In the syntax of the sort() function, there are three parameters passed in the function. Let’s see them in detail:
first: The first parameter is an iterator that points to the first element in the range that you want to sort. The first parameter marks the start of the range for sorting. It could be an iterator pointing to:
The first element of an array (like arr)
The beginning of a container such as a vector (vec.begin())
std::vector<int> vec = {5, 4, 1, 3};
std::sort(vec.begin(), vec.end()); // 'vec.begin()' is the iterator pointing to the first element of the vector
2. last: The last parameter is an iterator that points just past the last element in the range. The last parameter specifies the end of the range to be sorted. It’s important to note that the element at the position pointed to by last is not included in the sorting process. An iterator can be:
A pointer to just past the last element of an array (arr + n)
The iterator vec.end() in a vector, which points past the last element in the vector.
3. comp (optional): The sorting order is determined by this parameter, which is an optional comparison function, also known as a functor. A functor (object with operator()), a lambda expression, or a function pointer can be used. By defining the comparison between two components, you can create a custom sorting order using the comp option. Two items (a and b) are passed as parameters to this function, which returns:
True: If element a should come before b (according to your custom logic).
False: If element a should not come before b.
The comp parameter defaults to using the less-than (<) operator for ascending order.
Example:
std::sort(arr, arr + 4, [](int x, int y) {
return x > y; // Sorting in descending order
});
How does the sort() algorithm function work in C++?
The std::sort() function implements a set of different sorting methods to guarantee effectiveness, especially when dealing with large datasets. Internally, it uses a hybrid algorithm, mostly based on Introsort (or Introspective Sort), which switches between three other algorithms depending on the size and state of the dataset:
Quicksort (for most cases)
Heapsort (for worst-case scenarios)
Insertion Sort (for small datasets)
A hybrid strategy guarantees that std::sort() can retain a bound of O(n log n) for its time complexity while reducing the probability of ever experiencing the worst-case performance exhibited by quicksort.
Here is how these three algorithms work internally in the sort() function in C++:
Start with Quicksort: This algorithm first applies Quicksort to partition the array, followed by recursive calls to sort the sub-arrays.
How Quick Sort Works:
Partitioning: The array or range of elements is partitioned into two parts based on a pivot element. Elements smaller than the pivot are moved to its left, and elements greater than the pivot are moved to its right.
Recursion: The process is then recursively applied to the left and right sub-arrays until all sub-arrays are sorted.
Quicksort performs efficiently in most cases with an average time complexity of O(n log n). However, it can degrade to O(n^2) in certain worst-case scenarios (e.g., when the array is already sorted or nearly sorted and a poor pivot is chosen).
Switch to Heapsort: When the depth of the recursion stack exceeds a fixed limit, which hints that Quicksort will probably become inefficient, then the algorithm switches to Heapsort to keep a bound of O(n log n).
How Heap Sort Works:
Using the input array, heapsort first constructs a max-heap, which is a binary tree in which the parent node is always larger than its offspring.
Heap extraction involves rebuilding (heapifying) the heap for the remaining elements after the largest element, or the heap’s root is switched out for the final element.
Until the heap contains just one element, this process is repeated.
Heapsort ensures that the sort() function is still effective even in the worst-case scenario by guaranteeing a worst-case time complexity of O(n log n).
Use Insertion sort: In case there are several sub-arrays with a smaller size than say 16 elements, then the algorithm will apply the Insertion Sort.
How Insertion Sort Works:
Insertion Sort works by repeatedly taking the next unsorted element and inserting it into its correct position in the already sorted portion of the array.
Since it operates in O(n^2) time, it is not efficient for large datasets but works well for small ones due to its low overhead and simplicity.
The hybrid approach of combining Quicksort, Heapsort, and insertion sort ensures that std::sort() can perform effectively in all cases and keeps a balance between the speed and the worst-case performance.
The sort() function in C++ can be used with a variety of data types and scenarios. Here are the four main ways that the sort() method is implemented, based on usage:
Sorting integral data types
Sorting integral data types (like int, char, double) is the simplest use case for the sort() function. In this, we use whole numbers such as 1, 2, and so on to sort them directly.
Example:
#include <iostream> // import iostream
#include <algorithm> // Required for std::sort()
using namespace std;
int main() {
// Array of integers
int nums[] = {7, 23, 45 , 8, 12, 44, 19};
int n = sizeof(nums)/sizeof(nums); // Calculate the size of the array
// Sorting the array in ascending order
sort(nums, nums + n);
// Print the sorted array
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << nums[i] << " ";
}
cout << endl;
return 0;
}
Output:
Sorted array: 7, 8, 12, 19, 43, 44, 45
Sorting user-defined data types
User-defined data types, such as structs and classes, are more complicated to sort, and the sorting strategy usually needs to be defined by a custom comparator.
Example:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Define a structure to hold car data
struct MyStructure {
string name;
int year;
};
// Custom comparator function to sort cars by year in ascending order
bool compareMyStructure(MyStructure a, MyStructure b) {
return a.year < b.year; // Sort by year
}
int main() {
// Vector of cars
vector<MyStructure> cars = {{"Volvo", 1990}, {"Mercedes", 1992}, {"BMW", 2002}};
// Sort the vector of cars using the custom comparator
sort(cars.begin(), cars.end(), compareMyStructure);
// Output the sorted cars
cout << "Sorted cars by year: " << endl;
for (const auto& car : cars) {
cout << car.name << " - " << car.year << endl;
}
return 0;
}
Output:
Sorted cars by year:
Volvo - 1990
Mercedes - 1992
BMW - 2002
Sort using a function object
An object with function-like behaviour is called a functor or function object. It is employed in sorting logic for custom comparisons.
Example:
#include <iostream>
#include <algorithm>
#include <vector>
// Functor (Function Object) to sort in descending order
struct MyStructure {
// Overload the () operator to act as a comparison function
bool operator()(int a, int b) const {
return a > b; // Return true if a is greater than b (descending order)
}
};
int main() {
std::vector<int> nums = {34, 35, 23, 12, 66, 76};
// Sorting the vector using the function object
std::sort(nums.begin(), nums.end(), MyStructure());
// Output the sorted array
std::cout << "Sorted in descending order: ";
for (int num : nums) {
std::cout << num << " ";
}
return 0;
}
Output:
Sorted in descending order: 76 66 35 34 23 12
Sort using the lambda expression
Lambda expressions, which enable inline function declarations, were introduced in C++11. They are frequently used in sorting to build the custom comparators.
Example:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Define a structure to hold car data
struct MyStructure {
string name;
int year;
};
int main() {
// Vector of cars
vector<MyStructure> cars = {{"Volvo", 1990}, {"Mercedes", 1992}, {"BMW", 2002}};
// Use lambda function for sorting in ascending order of names
sort(cars.begin(), cars.end(), [](MyStructure a, MyStructure b) {
return a.name < b.name; // Sort by name
});
// Output the sorted cars
cout << "Sorted cars by year: " << endl;
for (const auto& car : cars) {
cout << car.name << " - " << car.year << endl;
}
return 0;
}
Output:
Sorted cars by year:
BMW - 2002
Mercedes - 1992
Volvo - 1990
Complexity Analysis of sort() function
Time Complexity
Best Case Complexity: O(n log n)
In the best case, Quicksort can perfectly partition the array at each step – dividing it into two halves, therefore its linear time complexity is O(n).
Insertion sort provides further optimization to lower usage, wherein portions are to be sorted, and hence overhead in sorting small pieces is negligible.
Average Case Complexity: O(n log n)
The std::sort() will run on average in O(n log n) over many uses.
Typically, the quicksort will efficiently partition the array most of the time, and the mix with heapsort will ensure that even when it doesn’t, the worst case, which degrades to O(n^2), does not do so in real-world cases.
The use of insertion sort for small partitions also keeps the overhead low.
Worst Case Complexity: O(n log n)
The reason std::sort() has a worst-case time complexity of O(n log n) is because when it runs unbalanced partitioning, it can run into worst-case quicksort behaviour and eventually degrade into IntroSort to Heapsort.
Space Complexity
In-Place Sorting (O(1) Extra Space):
One other major advantage of std::sort() is that it performs sorting in place, which means that no extra memory is allocated to store the sorted array as it is already stored in some auxiliary variables
So the space complexity for std::sort() comes out to be O(1) regarding auxiliary space.
However, recursion in quicksort uses the call stack so it has some overhead because the recursive calls are much lighter in weight. The maximum recursion depth for quicksort is O(log n); this gets reduced even further by switching to heapsort because heapsort does not use recursion.
Call Stack Memory (O(log n)):
Both Introsort and Quicksort can indirectly cause stack overflow with extremely deep recursion in worst-case scenarios, as a direct implementation would, but Introsort controls its recursion and then only log n calls deep before abandoning quicksort in favour of Heapsort, which is not recursive.
In this manner, it guarantees that the amount of call stack space used is, and therefore the overall space complexity is kept low.
A custom comparator in the sort() function provides how the comparison between two elements should be carried out when the sorting process is executed. This provides flexibility with sorting based on any criteria. For example, sorting in descending order, sorting complex data types (like structs), or sorting by specific fields.
Example: Sorting array in descending order using custom comparators
By default, std::sort() arranges elements in ascending order, but with the help of a custom comparator, we can sort elements in descending order.
#include <iostream>
#include <algorithm> // For std::sort
using namespace std;
int main() {
int arr[] = {7, 8, 1, 5, 2, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
// Sort in descending order using a custom comparator
std::sort(arr, arr + n, [](int a, int b) {
return a > b; // Returns true if 'a' should come before 'b' (larger first)
});
// Display sorted array
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
return 0;
}
Output:
8 7 7 6 5 2 1
Explanation:
The array `arr` is defined with some input elements.
We have passed a lambda function as a comparator where a > b implies sorting in descending order.
We have used the sort() comparator to sort the array.
Partial sorting in C++
Partial sorting is useful when you want only part of the array or container to be sorted. The standard library provides two key functions for partial sorting: std::partial_sort() and std::nth_element().
Example 1: Sort the first K elements using std::partial_sort() in C++
std::partial_sort() sorts the first k elements of the container, while what follows them is not sorted.
#include <iostream>
#include <vector>
#include <algorithm> // For std::partial_sort
using namespace std;
int main() {
vector<int> vec = {10, 2, 14, 4, 7, 12, 6};
// Partial sort: sort only the first 5 elements in ascending order
std::partial_sort(vec.begin(), vec.begin() + 5, vec.end());
// Output the partially sorted vector
for (int num : vec) {
cout << num << " ";
}
return 0;
}
Output:
2 4 6 7 10 14 12
Explanation:
The vector `vec` is defined with some input elements.
std::partial_sort() sorts the first k elements i.e., 5 elements here (from vec.begin() to vec.begin() + 4). The rest of the elements are left unsorted.
Finally, the output shows the vector arranged in k sorted manner: 2 4 6 7 10 14 12.
Example 2: Sort using std::nth_element() in C++
std::nth_element() rearranges the elements so that the element in the n-th position is the element that would be in that position if the array were fully sorted. All smaller elements precede the n-th element, and all larger elements follow it.
#include <iostream>
#include <vector>
#include <algorithm> // For std::nth_element
using namespace std;
int main() {
vector<int> vec = {10, 2, 14, 4, 7, 12, 6};
// Arrange elements so that the 4th element is in its sorted position
std::nth_element(vec.begin(), vec.begin() + 3, vec.end());
// Output the partially arranged vector
for (int num : vec) {
cout << num << " ";
}
return 0;
}
Output:
2 4 6 7 14 12 10
Explanation:
The vector `vec` is defined with some input elements.
std::nth_element() arranges the vector so that the element at the 4th position (vec.begin() + 3) is in its correct sorted position. Elements before it are smaller, and elements after it are larger.
Finally, the output shows the vector partially arranged: 2 4 6 7 14 12 10. The element 7 is in its sorted position, but the rest are not fully sorted.
Handling Edge Cases in Sorting
When implementing a sorting algorithm, there are chances that you sometimes miss any edge cases which in turn results in incorrect output or inefficient results. Here are some common edge cases encountered and handled in sorting:
Empty Array or List
Sorting an empty array or list is a common edge case. More importantly, at the trivial level, the sorting function should not handle this case incorrectly, for example, by causing errors like segmentation fault or violation of access.
Example:
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> arr; // Empty vector
std::sort(arr.begin(), arr.end()); // Handles empty case without issue
if (arr.empty()) {
std::cout << "Array is empty!" << std::endl;
} else {
for (int num : arr) {
std::cout << num << " ";
}
}
return 0;
}
How to handle it?
std::sort() in C++, handle empty arrays implicitly by performing no operations and returning immediately.
2. Array with One Element
A one-element array or list does not need to be sorted because it is already technically “sorted.” However, the sorting function should gracefully handle this case and not break or result in errors.
Example:
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> arr = {10}; // Single-element array
std::sort(arr.begin(), arr.end()); // No sorting necessary
for (int num : arr) {
std::cout << num << " ";
}
return 0;
}
How to handle it?
std::sort() efficiently handles this case by performing no unnecessary operations.
3. Array with reverse order
For the worst-case scenario, certain sorting algorithms like Bubble Sort and Insertion Sort will make the maximum number of comparisons and swaps. When the input array is in reverse order, for instance, [7, 6, 5, 4, 3].
Example:
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> arr = {5, 4, 3, 2, 1}; // Reversed order
std::sort(arr.begin(), arr.end()); // Handles reverse order efficiently
for (int num : arr) {
std::cout << num << " "; // Output: 1 2 3 4 5
}
return 0;
}
How to handle it?
std::sort() rearranges the elements to their correct order with minimal overhead, thereby handling them with the standard time complexity.
4. Sorting with Custom Comparators
Sorting with a custom comparator adds complexity since the function must handle correct ordering based on specific criteria. Mistakes in the custom comparator logic may result in incorrect sorting.
How to handle it?
With lambda expressions, function objects, or function pointers, users can build their comparison logic using sort().
5. Sorting with Duplicates
When an array contains duplicate values, the sorting function should be stable if required (i.e., equal elements should retain their original relative order). Some algorithms are inherently stable, while others are not.
Algorithms such as Merge Sort or std::stable_sort() should be used for stable sorting. Standard sorting algorithms such as Quick Sort or Heap Sort can be used if stability is not a requirement.
Real-World Applications of Sorting
Below are the real-world applications of sorting:
Efficient Query Processing: In databases, sorting guarantees efficiency, especially in the process of query resolution. For instance, within the framework of SQL in case of usage of ORDER BY or GROUP BY clauses, data should be sorted in a specific way to conform to required conditions. The sorting saves the database from the need to constantly fetch records to meet the required order since the required order will have been met already when the records were fetched.
E-commerce Product Listings: In e-commerce sites, ‘sort by’ features are common where goods and services can be sorted according to price, reviews, staff choices, or how relevant it is to the customer. Customers can sort and filter products with ease making their experience better and productive.
Education: Sorting is used to rank students based on their performance, sorting exam results, schools and universities can generate rank lists, identify top-performing students, and determine eligibility for scholarships or special programs.
Training Data Preparation: An important step in getting ready datasets for machine learning models is sorting. For example, in k-nearest neighbours (k-NN) classification, the algorithm chooses the top “k” closest neighbours by sorting data points according to their distance from a specific query point.
Load balancing: In cloud computing, sorting is used to effectively divide workloads among several servers. Cloud providers can optimise resource utilisation and minimise delays by allocating workloads to the most suitable servers by classifying jobs based on resource requirements.
Search Result Ranking: When using search engines such as Google, etc, sorting is common and enables the search results to appear in the order best suited to the consumers, based on keyword targeting, validity of the searched instance, and the strength of the page. These engines apply several sorts of strategies to ensure that the most accurate results are at the top of the list.
Sorting for Data Preprocessing: In large datasets, the act of sorting tends to be one of the most important data cleaning activities that acts as a foundation for every other activity performed on the dataset in many big data contexts. This is very much so in machine learning when sorting will be needed to prepare the dataset for feature extraction, clustering, or even regression models.
Time Complexity: As compared to all the other sorting algorithms which are based on comparisons, the average case and worst case time complexity of std: sort() which is O(n log n) is expected and is said to be optimal. Most of the real-life problems work in a highly optimised manner which makes std: sort() much faster than a lot of manual sorting algorithm implementations.
Space Complexity: std: sort() is an in-place sorting algorithm, meaning sorting can be achieved with O(1) additional memory. This is a big advantage as compared to other algorithms such as that of merge sort which possesses O(n) extra space requirement.
Applicability: Any container that has random-access iterators can be used with std: sort(), this includes matrices (std:: array), vectors (std:: vector), deques (std:: deque), and many others.
Performance Consistency: There are two trustable facts regarding std: sort(), first it always performs in O(n log n) in the average case as well as in the worst case which is certainly better than that of basic quicksort which has O(n²) in the worst case scenario. Another uses a hybrid sorting algorithm known as Introsort, which is a mixture of quicksort, heapsort, and insertion sort.
Code Simplicity: Lengthy sorting algorithms written in another function could be a hassle. But with std: sort() and its ability to sort in a single line of code, the requirement of a long and complex sorting algorithm is removed. This increases the readability and maintainability of the code.
Cons
Stability: std::sort() is not stable which means it cannot retain the relative position of the ordered elements. For example, if two objects have the same value, their original order might change after sorting.
Random-access iterators: std::sort() can only be used with containers that provide random-access iterators, such as arrays and vectors. However, it cannot be used on data structures such as linked lists, std::list, or even std::forward_list containers.
Barriers involving Customization: By default, std::sort() does utilise (<) but that can be sometimes unsatisfying. Even though this can be addressed by making custom comparators or lambda functions, it leads to adding more code which can get messy at times.
Not Best Option for Small Data Sets: quite the opposite, std::sort() applies mostly to large datasets as with its hybrid algorithm some overhead will be introduced for very small datasets instead simpler algorithms like insertion sort are more advantageous for smaller data sets where simple algorithms may be better suited for the task at hand.
Challenges in large Data Sets: The management of recursion as a quick sort iteration of intosort may still create problems in a restrictive memory environment, especially large datasets since std::sort is an in-place implementation and therefore does not impose extra memory requirement for the sorting technique itself.
Conclusion
The sort() function in C++ is extremely powerful and can facilitate a wide range of sorting needs. Any integral types, user-defined data structures, or more complex criteria can be accommodated with flexibility and speed by the sort() function. A deep knowledge of custom comparators, lambdas, and function objects will allow you to manage far more complex sorting requirements.
Understanding this function can make your application high-performing with efficient and strong data handling. Planning to kickstart your tech career? Consider pursuing a Certificate Program in DevOps & Cloud Engineering offered by Hero Vired in collaboration with Microsoft.
FAQs
How does the std::sort() function handle duplicate elements in the container?
std::sort() maintains relative order for duplicate elements but does not make any promises about stability. Stability means a guarantee that when two elements are the same, their original relative order will be preserved. Since std::sort() is not stable, it might reorder equal elements. Therefore, If you need stability, use the std::stable_sort() function as it keeps duplicate elements in the same order they were in the original sequence.
What is introsort in the sort function in C++?
Introsort is the sorting algorithm used by std::sort() to perform sorting. It begins with Quicksort but switches to Heapsort after the recursion depth, which helps avoid worst-case performance issues that could occur with Quicksort. Additionally, once the problem size becomes smaller (usually below 16), it then switches to Insertion sort.
Which sorting algorithm does std::sort use?
The std::sort uses the Introsort algorithm, which is a hybrid sorting algorithm that takes advantage of both quicksort, heapsort, and insertion sort.
Quicksort for large disorderly containing arrays.
Heapsort is used only when quicksort's performance degrades to the worst-case scenario in terms of time.
Insertion sort is used for small subarrays, usually fewer than 16 elements. This guarantees fine performance when it comes to how fast it works on small-scale sorting.
So, this way, average performance is taken and maintained, but worst-case behaviour is also protected.
What are the parameters of the std::sort function in C++?
std::sort() function in C++ accepts three parameters at most:
First Iterator (first): It denotes the starting point of the range of elements to be sorted.
Last Iterator (last): It denotes the end of the range (exclusive) of elements to be sorted.
Optional Comparator (comp): A functor or customised comparison function that specifies how elements should be compared. Std::sort() compares elements in ascending order using the default operator (<) if no comparator is provided.
Which sorting algorithm is best?
The best sorting algorithm will depend on more specific requirements, which include the size and nature of the data and constraints such as stability, memory usage, and worst-case performance. For general-purpose usage, Introsort which is used in std::sort() is often the best choice because it combines Quicksort’s average performance with Heapsort’s worst-case guarantees and Insertion sort’s efficiency for small datasets.
Deploying Applications Over the Cloud Using Jenkins
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.
