C++ sort() in detail

Prerequisite:

Understanding these three sorting algorithms (Quicksort, Insertion sort, Heap sort) is necessary and understanding other sorting algorithms like merge sort, bubble sort would be a plus point.

Let’s know about sort() of c++ in depth. Sorting is nothing but arranging the dataset in a particular order either ascending or descending. sort() is the inbuilt function provided in c++ for sorting the dataset. sort() uses the Introsort algorithm internally which is explained below.

sort() takes 2 to 3 parameters.

• The first parameter is starting address of the dataset
• The second parameter is the ending address of the dataset
• the Third parameter is a comparator which is optional. Comparator tells how sorting is to be done.

Comparison of every two elements takes place while sorting a dataset(passing those 2 elements to the comparator and getting boolean value in return). We make use of the comparator function in comparing two elements and deciding how sorting is to be done.

comparator function returns boolean value taking two parameters (let’s say a, b). if the comparator returns false, two elements will be swapped relatively otherwise they will be not swapped.

Example :

let’s say we have to sort 1, 3,2 in ascending order. While comparing every two elements from the given data.

• Suppose the algorithm passed {3,2} to the comparator while comparing every two elements. We want them to be swapped if the first element is greater than the second element as we want them in ascending order. so the comparator function should return false for the above case. If the algorithm had passed {1,2} comparator should return true as swapping is not needed now(those two elements are already in ascending order).
• The above logic can be coded as below

boolean comparator(int a, int b){
  return (a<=b);
}

Introsort Algorithm:

This algorithm is a hybrid algorithm that uses three algorithms(Quicksort, Insertion sort, Heap sort) to sort the dataset given using efficient time and space.

Working of Introsort Algorithm:

Introsort algorithm starts with the Quicksort algorithm and shifts to other algorithms when needed. At first, the partition is done and one of the following three cases arises.

• If the partition size is such that there is a possibility to exceed the maximum depth limit then the Introsort switches to Heapsort. We define the maximum depth limit as 2*log(N)
• If the partition size is too small then Quicksort decays to Insertion Sort. We define this cutoff as 16 (due to research). So if the partition size is less than 16 then we will do insertion sort.
• If the partition size is under the limit and not too small (i.e- between 16 and 2*log(N)), then it performs a simple quicksort.

Reasons for shifting from Quicksort :

As the size of data increases,

• recursion stack space also increases
• chances of worst-case increases
• Quicksort can perform even worse than O(n²) algorithm when the data set is too small due t the extra hidden constant constant factor.

Following are some additional points from geeksforgeeks.org

1. Why is Insertion Sort used (and not Bubble Sort, etc)?

Insertion sort offers the following advantages.

• It is a known and established fact that insertion sort is the most optimal comparison-based sorting algorithm for small arrays.
• It has a good locality of reference
• It is an adaptive sorting algorithm, i.e- it outperforms all the other algorithms if the array elements are partially sorted.

2)Why is Heapsort used (and not Mergesort etc)?

This is sole because of memory requirements. Merge sort requires O(N) space whereas Heapsort is an in-place O(1) space algorithm.

3)Why is Heapsort not used in place of Quicksort when the partition size is under the limit ?

This question is the same as why Quicksort generally outperforms Heapsort?

The answer is, although Heapsort also being O(N log N) in average as well as worse case and O(1) space also, we still don’t use it when the partition size is under the limit because the extra hidden constant factor in Heapsort is quite larger than that of Quicksort.

Hi everyone! If you liked this article please support me by giving me a follow! I’m a new writer to medium (so I have not yet reached the 100 follower count) and I will be posting very frequently on my findings and learnings in the tech industry and beyond.

Thanks for reading again! ❤️