Немного про сортировки

Оглавление:
Сортировка пузырьком
Шейкерная (коктейльная) сортировка, она же сортировка перемешиванием
Сортировка вставками
Сортировка выбором
Сортировка слиянием
Сортировка подсчетом

Сортировка слиянием

Массив разбивается на две примерно равные части, затем каждая из них сортируется (рекурсивно). После этого два отсортированных подмассива сливаются в один. Для этого в каждом из двух сливаемых массивов смотрим на первый еще не взятый элемент, и меньший из них "берем". Когда один из подмассивов закончился, оставшиеся элементы второго записываются после последнего элемента первого.