An Assortment of Sorts

Several other sorts have similar asymptotic profiles to insertion sort, with different advantages and disadvantages.

• insertion sort: To sort $A[1]\ldots A[n]$, recursively sort $A[1]\ldots A[n-1]$. Then, bubble A[n] downward until it stops. T(n) = n + T(n-1). Worst case $\Theta(n^2)$, best case $\Theta(n)$on sorted list.
• selection sort: To sort $A[1]\ldots A[n]$, pick out the max in $\Theta(n)$. Move max to the end in one swap. Recurse on $A[1]\ldots A[n-1]$. T(n) = n + T(n-1). Running time is always $\Theta(n^2)$.Swaps $\Theta(n)$, which is asymptotically optimal.
• Bubble sort: Scan through the list over and over again swapping adjacent elements that are out of order. Like insertion sort only much slower.