Question:easy

Which sorting algorithm performs best for nearly sorted data?

Show Hint

Think which method makes almost no shifts when items are already close to place. Its best case is near linear.
Updated On: Jul 2, 2026
  • Bubble sort
  • Selection sort
  • Insertion sort
  • Quick sort
Show Solution

The Correct Option is C

Solution and Explanation

Idea: Match each algorithm's best-case behaviour to a nearly sorted input.

Insertion sort has a best-case cost that appears exactly when the data is already close to order:

\[T_{best} = O(n)\]

Each key needs only one or two comparisons before it settles, so the total work is nearly linear. By contrast, selection sort forces $n$ full scans no matter the arrangement, staying $O(n^2)$; bubble sort still swaps and passes repeatedly; and quick sort's pivoting gains nothing from pre-sortedness.

The one algorithm whose cost collapses toward linear on nearly sorted data is insertion sort.

\[\boxed{\text{Insertion sort}}\]
Was this answer helpful?
0