Given an array of integers, sort it using introsort sorting algorithm.

Introsort is an efficient in-place sorting algorithm, which usually beats all other sorting algorithms in terms of performance. Due to its high performance, it is used in a number of standard library sort functions, including some C++ sort implementations.

Introsort is a comparison sort, meaning that it can sort items of any type for which a *less-than* relation is defined. It is usually not a stable sort which means that if two elements have the same value, they might not hold the same relative position in the output as they did in the input.

Introsort is hybrid of quicksort and heapsort algorithm. A hybrid algorithm combines two or more other algorithms that solve the same problem, so that the resultant algorithm is better than the individual algorithms. Introsort begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted. When the number of elements is below some threshold, introsort can switch to a non-recursive sorting algorithm such as insertion sort that performs fewer swaps, comparisons or other operations on such small arrays.

Below is C++ implementation of the introsort algorithm is similar GNU Standard C++ library. It uses introsort with a maximum depth of `2×log _{2} n`, followed by an insertion sort on partitions smaller than 16. The quicksort algorithm is optimized by better pivot selection.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 |
#include <iostream> #include <algorithm> #include <cmath> using namespace std; // Function to perform insertion sort on the array a[] void insertionsort(int a[], int low, int high) { // start from the second element in the sub-array // (element at index 'low' is already sorted) for (int i = low + 1; i <= high; i++) { int value = a[i]; int j = i; // Find the index j within the sorted subset a[0..i-1] // where element a[i] belongs while (j > low && a[j - 1] > value) { a[j] = a[j - 1]; j--; } // Note that subarray a[j..i-1] is shifted to // the right by one position i.e. a[j+1..i] a[j] = value; } } // Function to partition the array using Lomuto partition scheme int partition(int a[], int low, int high) { // Pick rightmost element as pivot from the array int pivot = a[high]; // elements less than pivot will be pushed to the left of pIndex // elements more than pivot will be pushed to the right of pIndex // equal elements can go either way int pIndex = low; // each time we finds an element less than or equal to pivot, pIndex // is incremented and that element would be placed before the pivot. for (int i = low; i < high; i++) { if (a[i] <= pivot) { swap(a[i], a[pIndex]); pIndex++; } } // swap pIndex with Pivot swap (a[pIndex], a[high]); // return pIndex (index of pivot element) return pIndex; } // Quicksort randomized partition to rearrange the elements across pivot int randPartition(int a[], int low, int high) { // choose a random index between [low, high] int pivotIndex = rand() % (high - low + 1) + low; // swap the end element with element present at random index swap(a[pivotIndex], a[high]); // call partition procedure return partition(a, low, high); } // Function to perform heap sort on the given range of elements void heapsort(int *begin, int *end) { make_heap(begin, end); sort_heap(begin, end); } // Function to perform introsort on the array a[] void introsort(int a[], int *begin, int *end, int maxdepth) { // perform insertion sort if partition size is 16 or smaller if ((end - begin) < 16) { insertionsort(a, begin - a, end - a); } // perform heapsort if maximum depth is 0 else if (maxdepth == 0) { heapsort(begin, end + 1); } else { // otherwise perform quicksort int pivot = randPartition(a, begin - a, end - a); introsort(a, begin, a + pivot - 1, maxdepth - 1); introsort(a, a + pivot + 1, end, maxdepth - 1); } } int main() { int a[] = { 5, 7, -8, 9, 10, 4, -7, 0, -12, 1, 6, 2, 3, -4, -15, 12 }; int n = sizeof(a) / sizeof(a[0]); // get maximum depth int maxdepth = log(n) * 2; // sort the array using introsort algorithm introsort(a, a, a + n - 1, maxdepth); // print the sorted array for (int i = 0 ; i < n; i++) cout << a[i] << " "; return 0; } |

`Output:`

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

## Introsort Performance:

Introsort sorting algorithm provides both fast average performance and (asymptotically) optimal worst-case performance. Both the average case and worst case time complexity of Introsort is O(nlog(n)).

The auxiliary space required by introsort algorithm is O(n) for the recursive call stack when naive Quicksort algorithm is used. To keep the stack depth bounded by `O(log n)`, recur first into the smaller side of the partition, then use a tail call to recur into the other.

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

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

Nicely done.