Insertion sort works the way you sort playing cards in your hand, sliding each new card into place. It is fast on small or nearly sorted arrays, because each element moves only a short distance. Use it when the data is almost in order or very small, which is why library sorts switch to it for small pieces. On large random arrays it is O(n²), so use Arrays.sort instead.