Рекурсивное слияние массивов и нерекурсивное отличаются порядком выполнения действий. 1

Рекурсивное слияние (нисходящая сортировка слиянием) сначала упорядочивает первую половину массива, а затем рекурсивно берётся за вторую половину. 12 Рекурсивный алгоритм обходит дерево сверху вниз. 1

Нерекурсивное слияние (восходящая сортировка слиянием) выполняет серию проходов по массиву, которые сливают упорядоченные подмассивы, пока не останется только один. 12 Каждый элемент массива, за исключением, возможно, последнего, участвует в каждом проходе. 1 Восходящая сортировка слиянием соответствует обходу дерева по уровням, снизу вверх. 1

Таким образом, рекурсивное слияние ориентировано на обратный обход дерева, а нерекурсивное — на обход по уровням.