Internal implementation of std::sort()

std::sort()

std::sort() is a C++ Standard Library function that does comparison sorting.

Syntax

sort(start_address, end_address, comparator)

You can also try this code with Online C++ Compiler

Run Code

where,

start_address: the address of the array's first element.

end_address: the address of the array's last element.

Comparator: the comparison to be made with the array ( This argument is optional )

Example

#include <bits/stdc++.h>
using namespace std;
   
int main()
{
    int arr[] = {1, 12, 8, 9, 6, 4, 2, 10, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
   
    sort(arr, arr+n);
   
    cout << "\nAfter sorting using default sort, "
         "the array is : \n";
 
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
   
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

After sorting using default sort, the array is : 

1 2 4 6 8 9 10 11 12 

You can also try this code with Online C++ Compiler

Run Code

Time Complexity

Best Case – O(N log N)

Average Case- O(N log N)

Worse Case- O(N log N)

here N = the number of elements to be sorted. 

Sorting Used by std::sort()

Sort() use the IntroSort algorithm. Introsort, a hybrid sorting algorithm, employs three sorting algorithms to reduce running time: Quicksort, Heapsort, and Insertion Sort. Simply said, it is the most incredible sorting algorithm available. It is a hybrid sorting algorithm, employing many sorting algorithms as part of its routine.

Introsort

The C++ implementation of the introsort algorithm that follows is comparable to the GNU Standard C++ library. It employs introsort with a depth limit of 2.log(n), followed by an insertion sort on smaller partitions less than 16. 

Code

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
 
// Function that performs insertion sort on given array "a" from index left to right.
void InsertionSort(int arr[], int left, int right)
{
    // element at index `left` is already sorted so 
    //start from the second element in the subarray
    for (int i = left + 1; i <= right; i++)
    {
        int value = arr[i];
        int j = i;


        while (j > left && arr[j - 1] > value)
        {
            arr[j] = arr[j - 1];
            j--;
        }
 
        //array is shifted to the right by one value.
 
        arr[j] = value;
    }
}
 
// Function that partition the Array
int partition(int arr[], int left, int right)
{
    // Picking the rightmost array element as a pivot.
    int pivot = arr[right];
 
    // elements less than the pivot will be pushed to the left of `pivotIndex`
    // elements greater than the pivot will be pushed to the right of `pivotIndex`
    int pivotIndex = left;
 
    //whenever we find an element less than or equal to the pivot, `pivotIndex`
    // is incremented by one, and that element is placed before the pivot.
    for (int i = left; i < right; i++)
    {
        if (arr[i] <= pivot)
        {
            swap(arr[i], arr[pivotIndex]);
            pivotIndex++;
        }
    }
 
    // swap `pivotIndex` with pivot
    swap (arr[pivotIndex], arr[right]);
 
    // return `pivotIndex` 
    return pivotIndex;
}
 
//Rearrange element with respect to pivot(Random)
int randPartition(int arr[], int left, int right)
{
    // choose a random index between `[left, right]`
    int pivotIndex = rand() % (right - left + 1) + left;
 
    // swap the right element with the element present at a random index
    swap(arr[pivotIndex], arr[right]);
 
    // calling the partition procedure
    return partition(arr, left, right);
}
 
// Function that performs perform heapsort
void heapSort(int *left, int *right)
{
    make_heap(left, right);
    sort_heap(left, right);
}
 
//introsort Function
void introSort(int arr[], int *left, int *right, int maxdepth)
{
    // performing insertion sort if partition size smaller(say 16)
    if ((right - left) < 16) {
        InsertionSort(arr, left - arr, right - arr);
    }
    // perform heapsort if the maximum depth is 0
    else if (maxdepth == 0) {
        heapSort(left, right + 1);
    }
    else {
        // else perform Quicksort
        int pivot = randPartition(arr, left - arr, right - arr);
        introSort(arr, left, arr + pivot - 1, maxdepth - 1);
        introSort(arr, arr + pivot + 1, right, maxdepth - 1);
    }
}
 
int main()
{
    int arr[] = { 2, 3, -8, 9, 10, 0, 5, 7,-12, 1, -4, 12 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // get the maximum depth
    int maxdepth = log(n) * 2;
 
    // sort the array using introsort the algorithm
    introSort(arr, arr, arr + n - 1, maxdepth);
 
    // print the sorted array
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
 
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

-12 -8 -4 0 1 2 3 5 7 9 10 12 

This example for a Program to sort the array using Introsort. The most popular C++ STL Algorithm- sort() uses Introsort.

Frequently Ask Questions

Which one is the best sorting algorithm?

Ans: Quicksort is one of the most efficient sorting algorithms, making it one of the most used. The 1st step is to choose a pivot number. This number will separate the data. On its left are the numbers smaller than it and the more significant numbers on the right.

What are the Sorting integral data types? 

Ans: Integral data types, such as 1,2, and so on, or, in other words, whole numbers, will be used in this type.

What is the Sorting using the Lambda Expression? 

Ans: In this type, you will directly inject the function into the places where the object is called. Instead of creating a separate function block, you can use the function body now to do the expression and call it in the main function. We can directly add them to the main function itself.

Conclusion

In this blog, we extensively discussed the internal implementation of std::sort() and learned about introsort. How it works, which algorithm it uses, and its implementation.

We hope that our blog enhances your knowledge regarding the Internal implementation of std::sort().

See Basics of C++ with Data Structure, DBMS, Operating System by Coding Ninjas, and keep practicing on our platform Coding Ninjas Studio.

Recommended Problems - 

• Sort 0 1 2 
• Wiggle sort
• Find first and last position in sorted array

If you think you are ready for the tech giants company, check out the mock test series on code studio.

You can also refer to our Guided Path on Coding Ninjas Studio to upskill yourself in domains like Data Structures and Algorithms, Competitive Programming, Aptitude, and many more!. You can also prepare for tech giants companies like Amazon, Microsoft, Uber, etc., by looking for the questions asked by them in recent interviews. If you want to prepare for placements, refer to the interview bundle. If you are nervous about your interviews, you can see interview experiences to get the ideas about these companies' questions.

Nevertheless, you may consider our premium courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!