Because O() notation ignores a constant multiplier (and usually overhead for memory allocation/function calls), when n is small, the selection sort can actually be more efficient. For example, selection sort's efficiency might be 10 n^2 and merge might be 100 n log n. For n=2, that's 40 verses 60.
There are also times when you have to look at whether merge sort is *significantly* more efficient, given the addition coding time that may be involved.
|