When would you use Selection sort versus Merge sort?

Question

Efficiency of Merge sort (nlogn) is always faster then Selection sort (n^2). When would you ever choose selection over merge sort?

Answer 1

Because the runtime of selection sort is Θ(n²) and the runtime of mergesort is O(n log n), for sufficiently large inputs mergesort will outperform selection sort. However, there are two areas in which selection sort might be better:

1. Selection sort on an array can be implemented with O(1) auxiliary storage space, whereas (most) implementations of mergesort on arrays use Θ(n) auxiliary storage space. As a result, if memory is extremely scarce, selection sort would be a better choice than mergesort. (However, it would be a worse choice than, say, heapsort or quicksort!)

2. Selection sort may be faster than mergesort on small input arrays because it's a simpler algorithm with lower constant factors than the ones hidden by mergesort. If you're sorting, say, arrays of 16 or so elements, then selection sort might be faster than mergesort. (However, it would probably be a worse choice than, say, insertion sort).

So in other words, there are some cases where selection sort would be better than mergesort, but in those cases you're still probably better off using another sorting algorithm. :-)