On 2016-Apr-20 08:45:00 +0200, Hans Petter Selasky <h...@selasky.org> wrote: >There is something which I don't understand. Why is quicksort falling >back to insertion sort which is an O(N**2) algorithm, when there exist a >O(log(N)*log(N)*N) algorithms, which I propose as a solution to the >"bad" characteristics of qsort.
O() notation just describes the (normally, worst case) ratio of input size to runtime for a given algorithm: Increasing the input size by (say) 100× means an insertion sort will take about 10000× as long to run, whilst the "best" algorithms would take about 2000× as long. It says nothing about how fast sorting (say) 1000 items takes with either sort or how they behave on "typical" inputs. In general, the fancier algorithms might have better worst-case O() numbers but they have higher overheads and may not perform any better on typical inputs - so, for small inputs, insertion sort or bubble sort may be faster. IMO: - If you're only sorting a small number of items and/or doing it infrequently, the sort performance doesn't really matter and you can use any algorithm. - If you're sorting lots of items and sort performance is a real issue, you need to examine the performance of a variety of algorithms on your input data and may need to roll your own implementation. As long as qsort() behaves reasonably and its behaviour is documented sufficiently well that someone can decide whether or not to rule it out for their specific application, that is (IMHO) sufficient. -- Peter Jeremy
Description: PGP signature