what is the worst case of insertion sort ?

  • 5
    $\begingroup$ What did the magic google oracle say? $\endgroup$ – Luke Mathieson May 15 '15 at 13:01
  • $\begingroup$ Wow, the magic Google oracle makes it work fast - the answer is even in the preview... $\endgroup$ – Evil Jul 28 '16 at 14:42
  • $\begingroup$ Try to google before you ask it here... $\endgroup$ – Maharaj Jul 29 '16 at 6:07

Wiki it:

It is O(n^2) or quadratic running time. It is more efficient in practice than selection sort and bubble sort despite the same time complexity as them.

The idea is that you need to take any element and shift elements over so that the sequence of element gradually start to look like it is in order.

You need to iterate n times in the array but do (n-1) shift per iteration.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.