[CygnetGames]

Another problem with just looking at time complexity is that in practice you may be concerned with space complexity as well. In functional languages, merge sorts are usually better for space than insertion sort, but in popular languages like C++ etc. implementing a merge sort usually requires more space than an insertion sort.

An example of when the constant multipiler is really important is with analogue computers. Using an analogue computer made of spaghetti it is possible to sort a list of numbers in linear time! (and linear space) But the problem is that it is such a task to actually build a machine that sorts using spaghetti. The constant multiplier is too high.

Also, if you know that your list is nearly sorted then insertion sort will do less work than merge sort. In my computer science course, we were advised to use insertion sort for small arrays. For medium-sized arrays, we were advised to start with quicksort but not take it all the way. If you stop a few iterations before quicksort is finished, you have a nearly-sorted array so it will be better to use insertion sort. For large arrays, shell sort was recommended. Not sure how widely-used these ideas are.