Introsort Algorithm: Overview & Implementation

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×log2 n, followed by an insertion sort on partitions smaller than 16. The quicksort algorithm is optimized by better pivot selection.

Download   Run Code

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

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

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

avatar
  Subscribe  
newest oldest most voted
Notify of
Ashley
Guest

Nicely done.