Feb. 21, 2014, 4:21 p.m. by Rosalind Team
Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time.
It is much less efficient on large lists than more advanced algorithms such as “Quick Sort”, “Heap Sort”, or “Merge Sort”.
However, insertion sort provides several advantages: simple implementation, efficient for (quite) small data sets,
When humans manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort.
Although it is one of the elementary sorting algorithms with
For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as “Merge Sort” or “Quick Sort”.
Visualization by David R. Martin: http://www.sorting-algorithms.com/insertion-sort
Insertion sort is a simple algorithm with quadratic running time that builds the final sorted array one item at a time.
Given: A positive integer
Return: The number of swaps performed by insertion sort algorithm on
6 6 10 4 5 1 2
For this problem, it is enough to implement the pseudocode above with a quadratic running time and to count the number of swaps performed. Note however that there exists an algorithm counting the number of swaps in
$O(n \log n)$.
Note also that Insertion Sort is an in-place algorithm as it only requires storing a few counters.