O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

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

Insertion sort is simple to implement and a stable sorting algorithm. During the process of sorting, it creates a sorted subsequence. From the unsorted subpart of the sequence, it takes one value at a time in each pass and inserts it in the sorted part of the sequence, maintaining the order in the sorted subsequence. When the last element is inserted in the sorted subsequence, we get the final sorted sequence. Hence, for a sequence of N elements, it takes N-1 passes. Remember that it does not swap values like the bubble and selection sort algorithms, but it inserts values one by one in a sorted subsequence.

We can better understand the insertion sort mechanism with the following pass-by-pass diagram:

We have a sequence of integers ...

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