0

What is the running time of insertion sort if every item in the input array is, say, at most 10 positions out of place?

I know insertion sort is where you compare the adjacent elements starting from the first element and swap it if the latter element is bigger until it is all sorted, and the worst case is n2. However, I am not sure how to approach the case where each element is near the correct position to begin with.

ruakh
  • 175,680
  • 26
  • 273
  • 307
sctts-lol
  • 557
  • 5
  • 9
  • Maybe [this](https://stackoverflow.com/q/3255/1707353) will help? – Jeff Holt Jan 17 '20 at 22:03
  • 2
    Since insertion sort takes time proportional to how far each element has to be swapped back to insert it into its right place, if that distance is bounded by a constant then the time complexity should be O(*n*). – kaya3 Jan 17 '20 at 22:20
  • Re: "I know insertion sort is where you compare the adjacent elements starting from the first element and swap it if the latter element is bigger until it is all sorted": No, that's [bubble sort](https://en.wikipedia.org/wiki/Bubble_sort). [Insertion sort](https://en.wikipedia.org/wiki/Insertion_sort) works quite differently (though it, too, has worst-case O(n²) runtime). – ruakh Jan 18 '20 at 02:10

0 Answers0