Read this in other languages: English, Português
Insertion sort is a comparison sorting algorithm that works similar to the way that some people sort cards in a bridge hand. When a new card should be inserted in the bridge hand, the player compares that new card with the others, to determine the right point of insertion.
- Partition the input array in two: (i) a sub-array
$A$ that initially contains only the first element of the input array; and (ii) a sub-array$B$ that initially contains all the remainder elements. - Take the first element of sub-array
$B$ and call it$x$ . - Search the sub-array
$A$ for the insertion point for$x$ , from right to left. - Shift one position to the right, all elements in the sub-array
$A$ that are left to the of the insertion point. - Insert
$x$ in the insertion position in$A$ . - If sub-array
$B$ is not empty, go to Step 2. - Return sub-array
$A$ , which contains all elements from the original array sorted.
- Best-Case:
$O(n)$ comparisons,$O(1)$ trocas. - Worst-Case:
$O(n^2)$ comparisons,$O(n^2)$ swaps.