# Introsort – Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Introsort”.

1. Why is heap sort preferred over merge sort for introsort implementation?
A) Because heap sort is faster
B) Because heap sort requires less space
C) Because heap sort is easy to implement
D) Because heap sort is easy to understand

Explanation: The time complexity of heap sort and merge sort is the same. However, heap sort is an in-place sorting algorithm, while merge sort necessitates O(n) auxiliary space, making heap sort the better option.

2. Why is insertion sort preferred over other sorting algorithms (like selection sort, bubble sort etc.) for introsort implementation?
A) Because insertion sort is faster and adaptive
B) Because insertion sort requires less space
C) Because insertion sort is easy to implement
D) Because insertion sort is easy to understand

Explanation: When it comes to sorting small arrays, insertion sort is the best choice. It’s also adaptive, so it outperforms most when the list is entirely or partially sorted.

3. What is the cut-off for switching from quick sort to insertion sort in the implementation of introsort?
A) 4
B) 8
C) 16
D) 32

Explanation: When small arrays need to be sorted, insertion sort is the most efficient method. Introsort moves to insertion sort when the partition size is less than 16. This value was calculated by experimentation.

4. What is the cut-off for switching from quick sort to heap sort in the implementation of introsort?
A) 16
B) n2
C) n log(n)
D) 2 log (n)

Explanation: Quicksort has an O(n2) worst-case time complexity, which is not ideal. When the depth is greater than 2 log, introsort switches to heap sort to prevent the worst case of quicksort (n). This value was calculated by experimentation.

5. Which of the following sorting algorithm will be preferred when the size of partition is between 16 and 2 log(n) while implementing introsort?
A) quick sort
B) insertion sort
C) heap sort
D) merge sort

Explanation: Because of its low space and time complexity, Quicksort is the best sorting algorithm for mid-sized arrays. When the partition size is between 16 and 2 log, simple sort is preferred (n).

6. What will be the output of the given C++ code?

#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = {1,3,4,2,5};
int n = sizeof(arr)/sizeof(arr[0]);
sort(arr, arr+n, greater<int>());
int a;
for (a = 0; a < n; a++)
cout << arr[a] << " ";
return 0;
}

A) 1 2 3 4 5
B) 1 3 4 2 5
C) 5 4 3 2 1
D) error

Explanation: The input is sorted in descending order by the specified programme. It’s because of the third parameter, greater(), that’s transferred to the sort feature ().

7. What will be the output of the given C++ code?

#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = {1, 3,4,2,5};
int n = sizeof(arr)/sizeof(arr[0]);
sort(arr, arr+n);
int a;
for ( a = 0; a< n; a++)
cout << arr[a] << " ";
return 0;
}

A) 1 2 3 4 5
B) 1 3 4 2 5
C) 5 4 3 2 1
D) error

Explanation: The input is sorted in ascending order by the specified programme. To sort an array, the function sort() takes two parameters in the form of the first and last element’s addresses.

8. What will be the output of the given C++ code?

#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = {1, 3,4,2,5};
int n = sizeof(arr)/sizeof(arr[0]);
sort(arr+2, arr+n, greater<int>());
int a;
for (int a = 0; a < n; a++)
cout << arr[a] << " ";
return 0;
}

A) 1 2 3 4 5
B) 1 5 4 3 2
C) 5 4 3 2 1
D) 1 3 5 4 2

Explanation: Since the first parameter to the sort() function is arr+2, sorting starts with the third element, i.e. 4. Also, since the function sort() has a third argument greater (), the sorting will be performed in descending order.

9. Which of the following sorting algorithm is used by C++ internally?
A) quicksort
B) introsort
C) merge sort
D) heap sort

Explanation: C++’s built-in sorting algorithm is called Introsort. It’s a hybrid sorting algorithm, which means it employs more than one sorting algorithm as a routine.

10. Which of the following sorting algorithm is not a constituent of introsort?
A) selection sort
B) quicksort
C) insertion sort
D) heap sort

Explanation: Introsort is a hybrid sorting algorithm, which means it employs many sorting algorithms. Depending on the case, it can use easy sort, heap sort, or insertion sort.

11. Introsort begins sorting the given array by using which of the following sorting algorithm?
A) selection sort
B) quick sort
C) insertion sort
D) heap sort

Explanation: Introsort uses fast sort to begin sorting any given list. Depending on the size of the partition, it can then default to heap sort, insertion sort, or fast sort.

12. Which of the following sorting algorithm is NOT stable?
A) Introsort
B) Brick sort
C) Bubble sort
D) Merge sort

Explanation: Introsort is the only algorithm that is not stable among the available choices. Since it can use fast sort to perform sorting in certain cases, which is inherently unstable. As a result, the reliability of introsort cannot be ensured.

13. Which of the following sorting algorithm is in-place?
A) intro sort
B) merge sort
C) counting sort

Explanation: Internally, Introsort can use fast sort, heap sort, or insertion sort to sort the provided input. Introsort is an in-place sorting algorithm where all three algorithms are implemented.

14. Introsort sort is a comparison based sort.
A) true
B) false

Explanation: Comparison-based sorts include quicksort, heap sort, and insertion sort. As a result, the overall introsort becomes a comparison-based sort.

15. What is the best case time complexity of introsort?
A) O(n)
B) O(n log n)
C) O(n2)
D) O(log n)

Explanation: Heap sort and fast sort are the most important aspects of introsort. Since the best case for heap and fast sort is O(n log n), the best case for introsort is also O(n log n) (n log n). public relations

16. What is the worst case time complexity of introsort?
A) O(n)
B) O(n log n)
C) O(n2)
D) O(log n)

Explanation: When we use introsort, we stop the worst-case time complexity of quicksort. When Introsort detects the probability of exceeding the maximum depth limit, it switches to heap sort.

17. What is the average time complexity of introsort?
A) O(n)
B) O(n log n)
C) O(n2)
D) O(log n)

Explanation: Introsort’s average time complexity remains O(n log n), so most of the time fast sort and heap sort are used, both of which have O(n log n) time complexity.

18. What is the auxiliary space requirement of introsort?
A) O(n)
B) O(n log n)
C) O(n2)
D) O(log n)

Explanation: Fast sort, heap sort, and insertion sort are all combined in Introsort. As with fast sort, it can store call statements in O(log n) auxiliary space in the stack.

Introsort, also known as introspective sort, is a hybrid sorting algorithm that offers both fast average and (asymptotically) optimal worst-case efficiency. It starts with quicksort, then moves to heapsort when the recursion depth reaches a threshold based on (the logarithm of) the number of elements to sort, and finally to insertion sort when the number of elements is less than a certain threshold. With realistic performance comparable to quicksort on standard data sets and worst-case O(n log n) runtime due to the heap sort, this algorithm combines the best parts of the three algorithms. It is also a comparison sort since the three algorithms it employs are comparison types.