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

который упорядочивает списки (или другие структуры данных, доступ к элементам

которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

(по 1 элементу), затем сравниваем каждый элемент с соседним, сортируем

и объединяем. В итоге, все элементы отсортированы и объединены вместе.