CREATE OWN LIBRARY

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. But, the worst-case complexity of quicksort is O(${\mathrm{n}}^2$). 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 

Quicksort:    https://mycareerwise.com/programming/category/sorting/quick-sort-using-recursion

Heapsort:   https://mycareerwise.com/programming/category/sorting/heap-sort-using-recursion

Insertion Sort:   https://mycareerwise.com/programming/category/sorting/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)

PROCESS:
Step 1: [Defining two macros max(a,b) and min(a,b)]
max(a,b) :	if (a>b) then 
return a
		else  		
return b
min(a,b) :	if (a<b) then 
return a
		else  	
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 
		break
	[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)
			return 
		[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)  
	else 
		[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.