Sorting Quiz

How many passes does an insertion sort algorithm consist of?

• n

• n-1

• n+1

Answer explanation

An insertion algorithm consists of N-1 passes when an array of N elements is given

What is the average case running time of an insertion sort algorithm?

Answer explanation

The average case analysis of a tight bound algorithm is mathematically achieved to be O(N²).

Insertion Sort is

• stable and sorts in place

• unstable and sorts in place

• stable and does NOT sort in place

• NOT stable and does NOT sort in place

Answer 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.

Which of the following sorting algorithm is best suited if the elements are already sorted?

• Insertion Sort

• Merge Sort

• Heap Sort

Answer 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).

Merge sort uses which of the following technique to implement sorting?

• backtracking

• greedy algorithm

• divide and conquer

• dynamic programming

What is the average case time complexity of merge sort?

What is the space complexity of merge sort?

What is the worst case time complexity of merge sort?

Which of the following is good for sorting arrays having less than 40 elements?

Time it takes to build a binary heap