Summary
By now, we have understood the sorting algorithms concept and have implemented all common sorting algorithms in C++. We have looked at the slowest sorting algorithms that give the time complexity as O(N2): bubble sort, selection sort, and insertion sort. However, if we are lucky, we can have a time complexity of O(N) for both bubble sort and insertion sort since they can detect whether we pass a sorted list. However, for selection sort, we will still have a time complexity of O(N2) even after the input list is sorted.
Other sorting algorithms that are faster than the three preceding algorithms are merge sort and quick sort. Their time complexity is O(N log N) since they have to divide the input list into two sublists. The last, and the fastest, sorting algorithm, are counting sort and radix sort since their time complexity is O(N).
In the next chapter, we are going to discuss a technique to search for an item in an array or a list by using a sorting algorithm.
