I need the asymptotic analysis for the following sorting algorithms.
Radix, Bucket, Heap, Merge.
The answer most be something more than "O(n log(n))". I need the whole
step by step mathematical procedure to get that result. Or references
to any book with the whole procedure.
I've checked McGraw Hill - Introduction To Algorithms, 2nd Edition.
but I need a deeper analysis.

---

Request for Question Clarification by mathtalk-ga on 24 Aug 2004 07:10 PDT

These are something of a mixed bag of algorithms.  I can point you to
a standard reference which is quite mathematical, but a radix sort is
a multi-pass (stable) bucket sort, and the complexity depends on how
many items accumulate in a "bucket" (ie. share a key or sub-key
value).

A side-by-side comparison of these algorithms requires, I think, a
definition of a particular sorting task to which all may be applied.

On the other hand if you are really looking for a comprehensive
mathematically oriented reference, I'll suggest Knuth's Art of Comp.
Prog. vol 3: "Sorting and Searching".

regards, mathtalk-ga

Are you sure you've priced this question correctly ?  That's a lot of work for $2.

You'll get a much better answer / attract far more interest if you
offer something more realistic.