Comparison Sort is a type of sorting algorithm that use simple comparisons such as larger than and lesser than. From 202201171853, while some of them would perform in \(O(N^2)\) in the worst case or even in average case, there are some could perform in \(O(N \log N)\) in the average case or even in the worst case.
The reason for this is that for naive approaches, it is inevitable that we need to do \(N^2\) comparisons on \(N\) elements since we need to compare element \(i\) to element \(i + k\). The examples for such algorithms are:
To improve this, we could simply eliminate more than one invertion or use divide-and-conquer algorithms to get a \(\Omega(N^2)\) or quicker running time. The examples for such algorithms are: