We have discussed sorting weapons used by different languages in previous article. In this article, C++’s Sorting Weapon, Introsort is discussed.

**What is Introsort?**

Simply putting, it is the best sorting algorithm around. It is a hybrid sorting algorithm, which means that it uses more than one sorting algorithms as a routine.

**Which standard sorting algorithms are used in Introsort**

Introsort being a hybrid sorting algorithm uses three sorting algorithm to minimise the running time, Quicksort, Heapsort and Insertion Sort

**How does it work?**

Introsort begins with quicksort and if the recursion depth goes more than a particular limit it switches to Heapsort to avoid Quicksort’s worse case O(N^{2}) time complexity. It also uses insertion sort when the number of elements to sort is quite less.

So first it creates a partition. Three cases arises from here.

- 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.

**Why is it better than simple Quicksort or Why the need of Introsort?**

Since Quicksort can have a worse case O(N^{2}) time complexity and it also increases the recursion stack space (O(log N) if tail recursion applied), so to avoid all these, we need to switch the algorithm from Quicksort to another if there is a chance of worse case. So Introsort solves this problem by switching to Heapsort.

Also due to larger constant factor, quicksort can perform even worse than O(N2) sorting algorithm when N is small enough. So it switches to insertion sort to decrease the running time of sorting.

Also if a bad pivot-selection is done then the quicksort does no better than the bubble-sort.

br>**Why is Insertion Sort used (and not Bubble Sort, etc)?**

Insertion sort offers 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.

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

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

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

This question is 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.

Why is cut-off 16 for switching from quick sort to insertion sort, and 2*logN for switching from quick sort to heap sort ?

These values are chosen empirically as an approximate because of various tests and researches conducted.

`/* A Program to sort the array using Introsort. ` ` ` `The most popular C++ STL Algorithm- sort() ` ` ` `uses Introsort. */` ` ` `#include<bits/stdc++.h> ` `using` `namespace` `std; ` ` ` `// A utility function to swap the values pointed by ` `// the two pointers ` `void` `swapValue(` `int` `*a, ` `int` `*b) ` `{ ` ` ` `int` `*temp = a; ` ` ` `a = b; ` ` ` `b = temp; ` ` ` `return` `; ` `} ` ` ` `/* Function to sort an array using insertion sort*/` `void` `InsertionSort(` `int` `arr[], ` `int` `*begin, ` `int` `*end) ` `{ ` ` ` `// Get the left and the right index of the subarray ` ` ` `// to be sorted ` ` ` `int` `left = begin - arr; ` ` ` `int` `right = end - arr; ` ` ` ` ` `for` `(` `int` `i = left+1; i <= right; i++) ` ` ` `{ ` ` ` `int` `key = arr[i]; ` ` ` `int` `j = i-1; ` ` ` ` ` `/* Move elements of arr[0..i-1], that are ` ` ` `greater than key, to one position ahead ` ` ` `of their current position */` ` ` `while` `(j >= left && arr[j] > key) ` ` ` `{ ` ` ` `arr[j+1] = arr[j]; ` ` ` `j = j-1; ` ` ` `} ` ` ` `arr[j+1] = key; ` ` ` `} ` ` ` ` ` `return` `; ` `} ` ` ` `// A function to partition the array and return ` `// the partition point ` `int` `* Partition(` `int` `arr[], ` `int` `low, ` `int` `high) ` `{ ` ` ` `int` `pivot = arr[high]; ` `// pivot ` ` ` `int` `i = (low - 1); ` `// Index of smaller element ` ` ` ` ` `for` `(` `int` `j = low; j <= high- 1; j++) ` ` ` `{ ` ` ` `// If current element is smaller than or ` ` ` `// equal to pivot ` ` ` `if` `(arr[j] <= pivot) ` ` ` `{ ` ` ` `// increment index of smaller element ` ` ` `i++; ` ` ` ` ` `swap(arr[i], arr[j]); ` ` ` `} ` ` ` `} ` ` ` `swap(arr[i + 1], arr[high]); ` ` ` `return` `(arr + i + 1); ` `} ` ` ` ` ` `// A function that find the middle of the ` `// values pointed by the pointers a, b, c ` `// and return that pointer ` `int` `*MedianOfThree(` `int` `* a, ` `int` `* b, ` `int` `* c) ` `{ ` ` ` `if` `(*a < *b && *b < *c) ` ` ` `return` `(b); ` ` ` ` ` `if` `(*a < *c && *c <= *b) ` ` ` `return` `(c); ` ` ` ` ` `if` `(*b <= *a && *a < *c) ` ` ` `return` `(a); ` ` ` ` ` `if` `(*b < *c && *c <= *a) ` ` ` `return` `(c); ` ` ` ` ` `if` `(*c <= *a && *a < *b) ` ` ` `return` `(a); ` ` ` ` ` `if` `(*c <= *b && *b <= *a) ` ` ` `return` `(b); ` `} ` ` ` `// A Utility function to perform intro sort ` `void` `IntrosortUtil(` `int` `arr[], ` `int` `* begin, ` ` ` `int` `* end, ` `int` `depthLimit) ` `{ ` ` ` `// Count the number of elements ` ` ` `int` `size = end - begin; ` ` ` ` ` `// If partition size is low then do insertion sort ` ` ` `if` `(size < 16) ` ` ` `{ ` ` ` `InsertionSort(arr, begin, end); ` ` ` `return` `; ` ` ` `} ` ` ` ` ` `// If the depth is zero use heapsort ` ` ` `if` `(depthLimit == 0) ` ` ` `{ ` ` ` `make_heap(begin, end+1); ` ` ` `sort_heap(begin, end+1); ` ` ` `return` `; ` ` ` `} ` ` ` ` ` `// Else use a median-of-three concept to ` ` ` `// find a good pivot ` ` ` `int` `* pivot = MedianOfThree(begin, begin+size/2, end); ` ` ` ` ` `// Swap the values pointed by the two pointers ` ` ` `swapValue(pivot, end); ` ` ` ` ` `// Perform Quick Sort ` ` ` `int` `* partitionPoint = Partition(arr, begin-arr, end-arr); ` ` ` `IntrosortUtil(arr, begin, partitionPoint-1, depthLimit - 1); ` ` ` `IntrosortUtil(arr, partitionPoint + 1, end, depthLimit - 1); ` ` ` ` ` `return` `; ` `} ` ` ` `/* Implementation of introsort*/` `void` `Introsort(` `int` `arr[], ` `int` `*begin, ` `int` `*end) ` `{ ` ` ` `int` `depthLimit = 2 * ` `log` `(end-begin); ` ` ` ` ` `// Perform a recursive Introsort ` ` ` `IntrosortUtil(arr, begin, end, depthLimit); ` ` ` ` ` `return` `; ` `} ` ` ` `// A utility function ot print an array of size n ` `void` `printArray(` `int` `arr[], ` `int` `n) ` `{ ` ` ` `for` `(` `int` `i=0; i < n; i++) ` ` ` `printf` `(` `"%d "` `, arr[i]); ` ` ` `printf` `(` ```
"
"
``` `); ` `} ` ` ` `// Driver program to test Introsort ` `int` `main() ` `{ ` ` ` `int` `arr[] = {3, 1, 23, -9, 233, 23, -313, 32, -9}; ` ` ` `int` `n = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]); ` ` ` ` ` `// Pass the array, the pointer to the first element and ` ` ` `// the pointer to the last element ` ` ` `Introsort(arr, arr, arr+n-1); ` ` ` `printArray(arr, n); ` ` ` ` ` `return` `(0); ` `} ` |

**Output:**

-313 -9 -9 1 3 23 23 32 233

Is Introsort stable ?

Since Quicksort is also not stable so Introsort is also __not__ stable.

**Time Complexity**

Best Case – O(N log N)

Average Case- O(N log N)

Worse Case- O(N log N)

where, N = number of elements to be sorted.

**Auxiliary Space**

Just like quicksort, it may use O(log N) auxiliary recursion stack space.

Know Your Sorting Algorithm | Set 2 (Introsort- C++’s Sorting Weapon)

**References**

https://en.wikipedia.org/wiki/Introsort

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

## leave a comment

## 0 Comments