Intro Sort

Back to Programming


Intro Sort is a hybrid sorting algorithm i.e. it uses more than one sorting algorithms to sort data which makes it one of the best sorting algorithms. Intro sort uses three sorting algorithms which help to minimize the running time of this algorithm. The three sorting techniques used are- Insertion Sort, Quick Sort, and Heap Sort.


The sorting starts with quicksort


If the recursion depth of the quicksort goes beyond a given limit, then it switches to heapsort to avoid the worst-case complexity of the quick sort algorithm. If the number of elements to be sorted is less then it uses insertion sort.


Please follow details about 





Insertion Sort:


INPUT:An unsorted array a[6,2,4,1,…………….,n]
OUTPUT:An sorted array a[1,2,3,4,5,…………..,n] (in ascending order)

Step 1: [Defining two macros max(a,b) and min(a,b)]
max(a,b) :	if (a>b) then 
return a
return b
min(a,b) :	if (a<b) then 
return a
return b

Step 2: [declaring swap function ‘void swap(int i, int j)’]
		Set temp <- a[i]
		Set a[i] <- a[j]
		Set a[j] <- temp
	[End of function ‘swap’]

Step 3:[ declaring maxHeap function ‘maxheap(int i, int b, int hn)’]
Set tmp <- a[b + i - 1]
while  i≤hn / 2
Set c <- 2 × i
	If c < hn and a[b + c - 1] < a[b + c] then
		Set c <- c+1 
	[End of ‘if’]
	if tmp ≥ a[b + c - 1] then 
	[End of ‘if’]
	Set a[b + i - 1] <- a[b + c - 1] 
	Set i <- c 
[End of ‘while’ loop] 
Set a[b + i - 1] <- tmp 
[end of function “maHeap()”] 

Step 4: [declaring heap function ‘heap(int b, int e, int hn)’]
	for i = hn/ 2 to  1 
		call maxHeap(i,b,hn) 
[end of ‘for’ loop] 

Step 5: [declaring heapSort function ’ heapSort(int b, int e)’]
		Set hn <- (e – b) 
	Call the function ‘heap(b, e, hn)’
	for i = hn to 1 repeat
		[moving current root to end] 
		Call the function ‘swap(b, b + i)’ 
		[calling ‘maxHeap()’ for the reduced heap] 
		Call the function ‘maxHeap(1, i, b)’
	[end of ‘for’ loop] 
[End of function’heapSort()’]

Step 6: [declaring insertionSort function ‘insertionSort(int l, int r)’]
		for i = l to r repeat
		Set k <- a[i] 
		Set j <- i 
		while j > l and a[j - 1] > k repeat
			Set a[j] <- a[j - 1] 
			Set j <- j-1 
		[end of ‘while’ loop] 
		Set a[j] <- k 
	[end of ‘for’ loop]
[End of ‘insertionSort()’]

Step 7: [declaring find_pivot function ‘find_pivot(int a1,int b1,int c1)’]
	Set mx <- max(max(a[a1], a[b1]), a[c1])
	Set mn <- min(min(a[a1], a[b1]), a[c1])
	Set median <- mx ^ mn ^ a[a1] ^ a[b1] ^ a[c1]
	if (median = a[a1])  then
		return a1 
	if (median = a[b1])  then
		return b1 
	return c1 
[end of function ‘find_pivot()’]

Step 8: [declaring partition function ‘partition(int l,int h)’]
	Set pivot <- a[h] 
	Set i <- (l - 1) 
	for j = l to h - 1 repeat
		if a[j] ≤ pivot then
			[incrementing the index of smaller element] 
			Set i <- i+1 
			swap(i, j) 
		[end of ‘if’] 
	[end of ‘for’ loop] 
	swap(i + 1, h) 
	return (i + 1) 
[end of function ‘partition()’]

Step 9: [declaring introsort function ‘introsort(int b,int e,int d’)]
	if e - b > 16 then 
		if (d = 0)  then
			[performing heap sort]
			Calling heapSort(b, e)
		[end of ‘if’] 
		Set d <- d - 1 
		Set pivot <- find_pivot(b, b + ((e - b) / 2) + 1, e)
		Calling swap(pivot, e) 
		Set p <- partition(b, e)
		Calling introsort(b, p - 1, d) 
		Calling introsort(p + 1, e, d)  
		[calling the insertion sort if the number of data is small]
		Calling insertionSort(b, e) 
	[End of ‘if’]
[End of function ‘introsort()’]

Step 10: [declaring sort function ‘sort()’]
	[initializing the depth] 
	Set d <- integer of (2 × floor(log(n) / log(2)))
	Calling introsort(0, n - 1, d) 
[end of function ‘sort()’]

Step 11: [declaring display function ‘display()’]
	for i=0 to n-1 repeat
		print a[i]
	[End of ‘for’ loop]
[End of ‘display()’]

Step 12: read n [number of elements]
	     For i=0 to n-1 repeat
		Read a[i]
	      [End of ‘for’ loop]
	      Call the function ‘sort()’
	      Call the function ‘display()’

Step 13: Stop.



1. It is a hybrid sorting algorithm i.e. it uses more than one sorting algorithm to sort the data.


2. It uses insertion sort, quick sort, and heap sort.


3. If the partition size is very small then it performs an insertion sort.


4. If the partition size is not very small but under the predefined limit then it performs quicksort.


5. If the partition size may go beyond the limit, then it performs heap sort.


6. It is a comparison-based sorting algorithm.



The intro is a combination of quick sort, heap sort, and insertion sort.


Time complexity of quicksort for best and average case is O(nlogn).


To seeing the time complexity of quicksort in details follow


Time complexity of heapsort for best, average and worst case is O(nlogn).


To seeing the time complexity of heapsort in details follow


Therefore, the time complexity of intro sort algorithm is O(nlogn) for all the three cases i.e. the best case, average case, and worst case.




2. Helps to apply a proper sorting algorithm.


3. It is an in-place sorting algorithm.



1. Intro sort is not a stable algorithm.


2. The logic is a little difficult than simple sorting algorithms.



1. The performance of the intro sort is very high for which it is used as standard library sort functions.

Contributed by