Introsort or introspective sort

Sorting Algorithm

1. COURSE TITLE: DATA STRUCTURES LABORATORY
COURSE CODE: CSE212

2. ID17010112, 3
RD SEMESTER, 29
TH BATCH
DEPARTMENT OF CSE, FSET, USTC

4. •It is a hybrid sorting algorithm that provides both fast average performance and
optimal worst-case performance .It begings with quicksort and switches to heapsort
when the recursion depth exceeds a level based on the number of elements being
sorted.This combines the good parts of both algorithms,with partical performance
compareable to quicksort on typical data sets and worst-case O(n log n)routine due
to the heap sort.Since both algorithms it uses are comparison sorts,it too is a
comparison sort.It is one of the fastest sorting algorithm in the world.

5. •Introsort being a hybrid sorting algorithm uses three sorting algorithm to minimise
the running time,quicksort,Heapsort and Insertionsort.
•Here i don't tell about insertion sort in first slide.It is the 3rd number of sorting
algorithm are used in introsort.i will tell about this algorithm in next slide.

6. •Introsort beings 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 quit
less.So first it creates a partition.Three cases arise from here.
•1.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).
•2.If the partition size is too small then Quicksort decays to insertion sort.We defines
this cutoff as 16.So if the partition size is less 16 then we will do insertion sort.
•3.If the partition size if under the limit and not too small (i.e-between 16 and
2*log(N)),then it performs a simple quicksort.

7. •Since Quicksort can have a worse case O(N^2) time complexity and it also increases
the recurtion 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 to 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.

8. •Insertion sort offers following advantages.
•1.It is a known and established fact that insertion sort is the most optimal
comparision-based sorting algorithm for small arrays.
•2.It has a good locality of reference.
•3.It is an adaptive sorting algorithm,i.e-it outerforms all the other algorithms if the
arrays elements are partially sorted.

9. •This is soley because of memory requirements.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?
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.

10. •Since Quicksort is also not stable so introsort is not stable.
•TIME COMPLEXITY:
•Best case- O(n log n)
•Average case- O(n log n)
•Worst case- O(n log n)
•where,N=number of elements to be sorted.
•AUXILIARY SPACE:
•Just like quicksort,it used O(n log n) auxiliary recursion stack space.

11. •Introsort begins with quicksort and switches to heapsort when the recursion depth
exceeds a level based on the number of elements being sorted.The point at which the
introsort algorithm switches from Quicksort to heapsort is determined by
depth_limit: depth_limit=2.[log2(l)]
•Where l is the length of the sequence that is to be sorted,so l=n for whole
sequence.With each recursive call depth_limit is decremented by one.When
depth_limit reaches 0,it switches from quicksort to heapsort.

12. •key attributes of this implementation:
•1. 3-way partition.
•2.median of three for pivot selection.
•3.sorting network for 1<=N<=6.
•4.insertion sort for 7<=N<=25.
•5.quicksort uses only one recursive call(the other one is transformed into tail recursion).
•6.Heapsort if quicksort degenerates (depth>2*log(n)).

13. •procedure: sort(A : array):
• let maxdepth =[log(lenth(A))] *2
• introsort(A, maxdepth)
•procedure: introsort(A, maxdepth):
• n length(A)
• p partition(A) //assume this function does pivot selection ,p is the final position of the pivot//
• if n<=1:
• return // base case
• else if p>maxdepth:
• heapsort(A)
•

14. •else:
• introsort(A[0:P] , maxdepth -1)
• introsort(A[p+1:n] , maxdepth -1)