Among the previous algorithms, quick sort performs worst in the worst case, while the others are always $O(n \log n)$. However, quick sort is known to be the fastest in practice for most inputs.

Heap sort is an in-place sorting algorithm that uses a heap data structure. It first transforms the list into a max-heap, then repeatedly pops the maximum value and places it at the end of the list. To build the heap in-place, the list is treated as a complete binary tree. With this assumption, it traverses from the bottom up and applies downHeap to convert the binary tree into a valid heap. This step takes $O(n \log n)$ (in fact, it is known to run in $O(n)$ with a careful analysis). After that, repeatedly swapping the root with the last element and restoring the heap property yields the sorted result. Overall, heap sort is an $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 select are algorithms based on the partition algorithm. The partition algorithm produces two sublists ($\mathcal{A},\mathcal{B}$) and one pivot value ($\gamma$). Every element in $\mathcal{A}$ is less than or equal to $\gamma$. Every element in $\mathcal{B}$ is greater than $\gamma$. Note that $\mathcal{A}$ may contain elements equal to $\gamma$ but not $\gamma$ itself, and either $\mathcal{A}$ or $\mathcal{B}$ may be $\emptyset$. As a result, the partition function places $\gamma$ as the maximum element of $\mathcal{A}$. Quick sort uses this property to sort the list. After partitioning, $\mathcal{A}$ and $\mathcal{B}$ are sorted relative to each other by $\gamma$. Therefore, quick sort simply recurses on $\mathcal{A}$ and $\mathcal{B}$. Quick select does a similar thing. Quick select is an algorithm to find the $n$-th element in the list. If the rank of $\gamma$ equals the target rank, we are done. If the rank of $\gamma$ is less than the target, adjust the target rank and recurse into $\mathcal{B}$. If the rank of $\gamma$ is greater than the target, adjust the target rank and recurse into $\mathcal{A}$. It works like a partial quick sort — it sorts just enough to locate the desired element.

Merge sort is a straightforward divide-and-conquer sorting algorithm. It requires $O(n)$ extra memory, unlike quick sort. However, it guarantees $O(n \log n)$ time complexity even in the worst case.