SORTING BY SELECTION

Offline algorithms

Selection sort
find maximum & replace with the concurrent last












$W(n)=O(n^{2})$
$S(n)=O(1)$
$O(n^{2})$ even on a sorted list

Tournament Sort


















$W(n)=A(n)=B(n)=O(n \log n)$
$S(n)=O(n)$ for the tournament tree

Heap Sort

• construct a max heap -$O(n)$
• delete root and update heap repeatedly -$O(n\log n)$

$W(n)=A(n)=O(n \log n)$
$S(n)=O(1)$