From the previous algorithms, qsort is the slowest at the worst cases and others are always $O(n logn)$. However, qsort is known to be fastest at the most of cases.

Heap sort is an in-place algorithm that sorts the list with heap. It first changes a list to the heap and then keeps poping it and push the maximum value to the end of the list. To change a list to the heap in-place, list is assumed to be form of complete binary tree. With this assumption, it read from bottom to up and downHeap to change complete binary tree to heap. This takes $O(n log n)$(Infact, it is known to be $O(n)$ with carefull analysis). After that, just pop head and push it to end of the list. As a result, it is $O(n log n)$ in-place sorting algorithm. ```python def downHeap(lst, length, idx): if 2 * idx + 2 < length: if lst[idx] < lst[2 * idx + 1]: if lst[2 * idx + 1] < lst[2 * idx + 2]: lst[idx], lst[2 * idx + 2] = lst[2 * idx + 2], lst[idx] downHeap(lst, length, 2 * idx + 2) else: lst[idx], lst[2 * idx + 1] = lst[2 * idx + 1], lst[idx] downHeap(lst, length, 2 * idx + 1) elif lst[idx] < lst[2 * idx + 2]: lst[idx], lst[2 * idx + 2] = lst[2 * idx + 2], lst[idx] downHeap(lst,length, 2 * idx + 2) elif 2 * idx + 1 < length: if lst[idx] < lst[2 * idx + 1]: lst[idx], lst[2 * idx + 1] = lst[2 * idx + 1], lst[idx] downHeap(lst, length, 2 * idx + 1) else: pass

Quick sort and quick selection are algorithms based on the partition algorithm. Partition algorithm makes a two sublist($\mathcal{A},\mathcal{B}$) and one value(pivot$ = \gamma$). Every element in $\mathcal{A}$ is less or equal than $\gamma$. Every element in $\mathcal{B}$ is greater than $\gamma$. Notice that $\mathcal{A}$ can have some elements which have the same value with $\gamma$ but not $\gamma$ itself and $\mathcal{A},\mathcal{B}$ may be $\emptyset$. As a result, partition function makes $\gamma$ is the highest value of $\mathcal{A}$. Quick sort uses this property to sort the list. After partition function, $\mathcal{A}$ and $\mathcal{B}$ is sorted to each other by $\gamma$. Therefore, quick sort just sort recursively in $\mathcal{A}$ and $\mathcal{B}$. Quick selection do the simillar thing. Quick selection is an algorithm to find a $n$th element in the entire list. If the order of $\gamma$ is equal with what you seek for, it’s done. If the order of $\gamma$ is less than what you seek for, adjust the order to find and try to check $\gamma$ in $\mathcal{B}$ again. If the order of $\gamma$ is greater than what you seek for, adjust the order to find and try to check $\gamma$ in $\mathcal{A}$ again. It works like semi-quick sort, it sorts a little bit and tries to find the elements in $n$th order and keep going on.

Merge sort is a naive way to sort with divide and conquer methodology. It needs $O(n)$ memory space unlike quick sort. However, it has only $O(n \log n)$ time complexity even at the worst-case.