A list is ordered from smaller to largest. Which sort would take the longest and shortest time to execute?

Question

both seems to be same, can someone explain the difference with example and complexity?

Answer 1

If we will compare by taking five sorting algo (Bubble, insertion, selection, merge, quick)

Then for already sorted order Bubble sort will take least time, as first pass only no swap will happen means list is already sorted.So best case will be O(n) , n is size of you list.

Worst case will be selection sort, as here every time you find your minimum element and place it in proper place, though already sorted you still have to check for minimum element in each traversal. so best case/ worst case is same O(n^2), selection sort will take more time to sort.

If you want to have graphical view you can visit this link
http://www.sorting-algorithms.com/nearly-sorted-initial-order