O'Reilly logo

Everyday Data Structures by William Smith

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

An insertion sort is a very simple algorithm that looks at an object in a collection and compares its key to the keys prior to itself. You can visualize this process as how many of us order a hand of playing cards, individually removing and inserting cards from left to right in ascending order.

For example, consider the case of ordering a collection in ascending order. An insertion sort algorithm will examine an object at index i and determine if it's key is lower in value or priority than the object at index i - 1. If so, the object at i is removed and inserted at i - 1. At this point, the function will repeat and continue to loop in this manner until the object key at i - 1 is not lower than the object key at i.

Given the following ...

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