Более теоретический ответ: рассмотрим различные алгоритмы сортировки (быстрая сортировка, сортировка слиянием, пузырьковая сортировка и т. Д.).
Из-за того, что мы знаем, что вы можете объединить два отсортированных списка за линейное время, распараллелить любой алгоритм сортировки довольно просто, поместив шаг «слияния» поверх него. Таким образом, существует множество вариантов, которые вы можете использовать для выполнения этой задачи.
Однако терасорт гораздо умнее этого, потому что простое расщепление и слияние не решат всех ваших проблем ... Ваш последний шаг "слияния" соответствует значительному шагу сокращения, когда у вас много расщеплений.