Существует ли нерекурсивный способ разделения каждого элемента списка на собственный список?

Question

Я просматривал псевдокод Википедии (и другие веб-страницы, такие как sortvis.org и sorting-algorithm.com) по сортировке слиянием и видел, что подготовка к слиянию использует рекурсию.
Мне было любопытно посмотреть, есть ли нерекурсивный способ сделать это.
Возможно, что-то вроде for each i element in list, i=[i-th element].

У меня сложилось впечатление, что рекурсия придерживайся минимума, потому что это нежелательно , и поэтому я подумала над этим вопросом.

Ниже приведен пример псевдокода рекурсивной части сортировки слиянием из Википедии:

function merge_sort(list m)
    // if list size is 1, consider it sorted and return it
    if length(m) <= 1
        return m
    // else list size is > 1, so split the list into two sublists
    var list left, right
    var integer middle = length(m) / 2
    for each x in m up to middle
         add x to left
    for each x in m after or equal middle
         add x to right
    // recursively call merge_sort() to further split each sublist
    // until sublist size is 1
    left = merge_sort(left)
    right = merge_sort(right)

Answer 1

Сортировка снизу вверх - это нерекурсивный вариант сортировки слиянием.

См. Также эту страницу википедии для более подробной реализации псевдокода.

Answer 2

В качестве отступления - рекурсия не является нежелательной сама по себе.

Рекурсия нежелательна, если у вас ограниченное пространство стека (вы боитесь stackoverflow ?; -)) или в некоторых случаях, когда накладные расходы на вызовы функций вызывают большую озабоченность.

В большинстве случаев эти условия не выполняются;удобочитаемость и удобство обслуживания вашего кода будут более актуальными.По моему мнению, такие алгоритмы, как сортировка слиянием, имеют больше смысла, если их выражать рекурсивно.

Answer 3

middle = len(lst) / 2
left = lst[:middle]
right = lst[middle:]

Список нарезки работает нормально.