Поскольку время выполнения сортировки выбора равно Θ (n 2 ), а время выполнения сортировки слиянием - O (n log n), для достаточно больших входных данных сортировка слиянием будет превосходить сортировку выбора. Однако есть две области, в которых сортировка выбора может быть лучше:
Сортировка выбора в массиве может быть реализована с O (1) вспомогательным пространством хранения, тогда как (большинство) реализаций mergesort для массивов используйте Θ (n) вспомогательного пространства памяти. В результате, если памяти очень мало, сортировка выбора будет лучшим выбором, чем сортировка слиянием. (Однако это был бы худший выбор, чем, скажем, heapsort или quicksort!)
Сортировка выбора может быть быстрее, чем сортировка слиянием на небольших входных массивах, потому что это более простой алгоритм с меньшими постоянными коэффициентами чем те, которые скрыты слиянием. Если вы сортируете, скажем, массивы из 16 или около того элементов, то сортировка выбора может быть быстрее, чем сортировка слиянием. (Однако, вероятно, это был бы худший выбор, чем, скажем, сортировка вставкой).
Другими словами, в некоторых случаях сортировка выбора будет лучше, чем сортировка слиянием, но в в этих случаях вам, вероятно, все-таки лучше использовать другой алгоритм сортировки. : -)