An inversion is a pair of elements which are not ordered with respect to an ordering relation.
Sorts which involve comparing elements.
Select the smallest element in the unsorted portion of the array and add it to the sorted portion of the array.
<aside> 💡
$\mathcal{O}(N^2)$ Time Complexity. Since, in the worst case, we need to iterate across $N + (N-1) + \dots + 2 + 1 \in \Theta(N^2)$ elements.
</aside>
<aside> 💡
$\Theta(1)$ Space Complexity. This is true if elements are swapped in place.
</aside>
Take the first element in the unsorted portion of the array and insert it in the correct index of the sorted portion of the array.
<aside> 💡
$\mathcal{O}(N + K)$ Time Complexity. Since each swap is guaranteed to reduce the number of inversions $K$ by $1$, this means that there is $K$ total swaps which occur across $N$ elements. However, typically $K \in \Theta(N^2)$, so this algorithm is only optimal for small or almost sorted lists.
</aside>
<aside> 💡
$\Theta(1)$ Space Complexity. Since swaps are done in place.
</aside>
Known as an adaptive sort because it takes advantage of pre-existing order in the list (in this case, the number of inversions).
Turn the array into a heap and continuously remove from it to build the sorted array.