CODEWITHSUNDEEP
sortinginsertion-sort
ueg1990
ueg1990

Reputation: 1033

Sorting almost sorted array using Insertion Sort

  1. Regarding insertion sort on almost sorted arrays, it takes linear time. But that is only after we have an if condition in our implementation to break out of loop if array is sorted, right??

  2. For insertion sort on small data sets, why is insertion sort preferrable? Because of the fewer amount of compariosns/operations comapred to quicksort and mergesort?

Upvotes: 0

Views: 1054

Answers (1)

stacktrace
stacktrace

Reputation: 319

Yes, it takes linear time on almost sorted arrays because you break out of the comparison loop very early. Once you insert the element in the right place, there is no need to go through the rest of the sorted array.

I guess it's because you're utilizing the knowledge about the already sorted array, whereas in quicksort, you get each element to the right place and then sort the remaining elements.

Upvotes: 1

Related Questions