Insertion Sort

Time complexity

O(N^2) (technically, it's O(N^2 + 2N - 2) in the worst case, and O(N^2 / 2) in the average case).

Mentioned in chapter 6 of a-common-sense-guide-to-data-structures-and-algorithms.

Insertion sort v. Selection sort

Which is better: selection-sort or Insertion Sort?

The answer is: well, it depends. In an average case—where an array is randomly sorted—they perform similarly. If you have reason to assume that you’ll be dealing with data that is mostly sorted, Insertion Sort will be a better choice. If you have reason to assume that you’ll be dealing with data that is mostly sorted in reverse order, Selection Sort will be faster. If you have no idea what the data will be like, that’s essentially an average case, and both will be equal.