# Insertion Sort Multiple choice Questions and Answers (MCQs)

## Click on any option to know the CORRECT ANSWERS

 Question 1
Which of the following is correct with regard to insertion sort?
 A insertion sort is stable and it sorts In-place B insertion sort is unstable and it sorts In-place C insertion sort is stable and it does not sort In-place D insertion sort is unstable and it does not sort In-place

Question 1 Explanation:
During insertion sort, the relative order of elements is not changed. Therefore, it is a stable sorting algorithm. And insertion sort requires only O(1) of additional memory space. Therefore, it sorts In-place.

 Question 2
Which of the following sorting algorithm is best suited if the elements are already sorted?
 A Heap Sort B Quick Sort C Insertion Sort D Merge Sort

Question 2 Explanation:
The best case running time of the insertion sort is O(n). The best case occurs when the input array is already sorted. As the elements are already sorted, only one comparison is made on each pass, so that the time required is O(n).

 Question 3
The worst case time complexity of insertion sort is O(n2). What will be the worst case time complexity of insertion sort if the correct position for inserting element is calculated using binary search?
 A O(nlogn) B O(n2) C O(n) D O(logn)

Question 3 Explanation:
The use of binary search reduces the time of finding the correct position from O(n) to O(logn). But the worst case of insertion sort remains O(n2) because of the series of swapping operations required for each insertion.

 Question 4
Insertion sort is an example of an incremental algorithm.
 A True B False

Question 4 Explanation:
In the incremental algorithms, the complicated structure on n items is built by first building it on n - 1 items. And then we make the necessary changes to fix things in adding the last item. Insertion sort builds the sorted sequence one element at a time. Therefore, it is an example of an incremental algorithm.

 Question 5
Consider the code given below, which runs insertion sort:

void insertionSort(int arr[],  int array....size) { int i,  j,  value; for (i = 1; i < array....size; i++) { value = arr[i]; j = i; while (..... ) { arr[j] = arr[j - 1]; j = j - 1; } arr[j] = value; } }

Which condition will correctly implement the while loop?

 A (j > 0) || (arr[j - 1] > value) B (j > 0) && (arr[j - 1] > value) C (j > 0) && (arr[j + 1] > value) D (j > 0) && (arr[j + 1] < value)

Question 5 Explanation:
In insertion sort, the element is A[j] is inserted into the correct position in the sorted sequence A[1... j - 1]. So, condition given in (j > 0) && (arr[j - 1] > value) will implement while loop correctly.

There are 5 questions to complete.