## Intro Sort

Back to Programming

### Description

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.

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

### Algorithm

``````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
[End of ‘for’ loop]
Call the function ‘sort()’
Call the function ‘display()’

Step 13: Stop.
``````

### Code

CHARACTERISTICS:

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.

TIME COMPLEXITY:

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

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

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

To seeing the time complexity of heapsort in details follow

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

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.

APPLICATIONS:

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

Related

Contributed by