Question

Which sorting algorithm performs best for nearly sorted data?

• A. Bubble sort
• B. Selection sort
• C. Insertion sort
• D. Quick sort

Hint:

Think which method makes almost no shifts when items are already close to place. Its best case is near linear.

Answer 1

The Correct Option is C

Step 1: Nearly sorted means most elements are already close to their final positions, so only a few small shifts are needed.

Step 2: Insertion sort picks each element and slides it left only until it meets a smaller element. If the data is nearly sorted, each element moves very little, often not at all.

Step 3: For an already-sorted or nearly-sorted array, insertion sort runs in close to linear time \(O(n)\), because the inner comparisons stop early.

Step 4: Selection sort always scans the full unsorted part regardless of order, so it stays \(O(n^2)\). Bubble sort can detect sortedness but still does more work per pass. Quick sort does not benefit from near-sortedness and can even degrade. Insertion sort is the best fit, so the correct option is (C).