Re: qsort() documentation

On 2016-Apr-20 08:45:00 +0200, Hans Petter Selasky <hps_at_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