Question

Which sorting algorithm has the best-case time complexity of $O(n)$ when the input array is already sorted?

• A. Merge Sort
• B. Quick Sort
• C. Insertion Sort
• D. Heap Sort

Hint:

Bubble Sort can also achieve $O(n)$ best-case complexity, but only if it includes a "flag" to detect if any swaps occurred during the first pass. Insertion Sort does this naturally.

Answer 1

The Correct Option is C

Concept: The efficiency of a sorting algorithm can vary significantly depending on the initial order of the data.
• Adaptive Algorithms: These algorithms run faster if the input is already partially or fully sorted.
• Best Case: The scenario where the least amount of work is performed.

Step 1: Evaluating non-adaptive sorts.
Merge Sort always performs $O(n \log n)$ work regardless of order. Heap Sort also maintains a consistent $O(n \log n)$ complexity.

Step 2: Analyzing Insertion Sort logic.
Insertion Sort builds the final sorted array one item at a time. For each element, it checks if the element is already in the correct position.

Step 3: Analyzing the sorted case.
If the array is already sorted, each element is compared only once with its predecessor. No swaps or shifts are necessary. Total comparisons = $n - 1$, which is $O(n)$.