How to profile sort algorithms?

I have coded a few sorting 开发者_开发技巧methods in C and I would like to find the input size at which the program is optimal (i.e.) profiling each algorithm. But how do I do this? I know to time each method, but I don't know how I can find the size at which it is 'optimal'.

---

It depends on some factors:

• Data behaviour: is your data already partially sorted? or it is very random?

• Data size: for a big input (say 1 thousand or more) you can assure that O(N^2) sorting methods will lose to O(N*log(N)) methods..

• Data structure of the data: is it array or list or ?. Sorting method with non sequential access to data will be slower for something like list

So the answer is by empirically running your program with some real data you will likely handle combined by varying in the input size.

When a slower method (like O(N^2)) gets beaten by some faster method (like O(N*log(N))) when input size is > X then you can say that the slower method is 'empirically optimal' for input size <= X (the value depends on the characteristics of the input data).

---

Sort algorithms do not have a single number at which they are optimal.

For pure execution time, almost every sort algorithm will be fastest on a set of 2 numbers, but that it not useful in most cases.

Some sort algorithms may work more efficiently on smaller data sets, but that does not mean they are 'optimal' at that size.

Some sorts may also work better on other characteristics of the data. There are sorts that can be extremely efficient if the data is almost sorted already, but may be very slow if it is not. Others will run the same on any set of a given size.

It is more useful to look at the Big O of the sort (such as O(n^2), O(n log n) etc) and any special properties the sort has, such as operating on nearly sorted data.

---

To find the input size at which the program is optimal (by which I assume you mean the fastest, or for which the sorting algorithm requires the fewest comparisons) you will have to test it against various inputs and graph the independent axis (input size) against the dependent axis (runtime) and find the minimum.