Algorithms Sorting & Searching Algorithms 2

Question 1

What is the space complexity of MergeSort?

Accepted Answer

O(n)

Answer

MergeSort requires O(n) auxiliary space to hold the temporary arrays used during the merge step.

Question 2

In HeapSort, what data structure is used to sort elements?

Accepted Answer

Max-Heap

Answer

HeapSort builds a max-heap from the input and repeatedly extracts the maximum element to sort the array.

Question 3

What is the time complexity of Counting Sort when the range of elements is k?

Accepted Answer

O(n + k)

Answer

Counting Sort runs in O(n + k) time by counting occurrences of each element and then reconstructing the sorted array.

Question 4

Which search algorithm requires the input list to be sorted before it can be applied?

Accepted Answer

Binary Search

Answer

Binary Search requires a sorted array because it relies on comparing the midpoint value to determine which half to discard.

Question 5

What distinguishes an in-place sorting algorithm from others?

Accepted Answer

It uses only a constant amount of extra memory

Answer

An in-place algorithm rearranges elements using O(1) extra memory beyond the input array itself.

Algorithms Practice Test