O'Reilly logo

A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Insertion Sort

We’ve previously encountered two different sorting algorithms: Bubble Sort and Selection Sort. Both have efficiencies of O(N2), but Selection Sort is actually twice as fast. Now we’ll learn about a third sorting algorithm called Insertion Sort that will reveal the power of analyzing scenarios beyond the worst case.

Insertion Sort consists of the following steps:

  1. In the first passthrough, we temporarily remove the value at index 1 (the second cell) and store it in a temporary variable. This will leave a gap at that index, since it contains no value:

    images/chapter7/new/optimizing_for_optimistic_scenarios-centered-no-text_Part1.png

    In subsequent passthroughs, we remove the values at the subsequent indexes.

  2. We then ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required