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

Question

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

Я нахожусь под впечатлением, что рекурсия Keep-он-к-а-минимум, потому что-это-нежелательные, и поэтому, следовательно, я думал об этом вопросе.

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

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

Bottom-up merge sort не является рекурсивным вариант сортировки слиянием.

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

Answer 2

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

Список нарезных работ отлично.

Answer 3

Отклонение - Рекурсия не является нежелательной как таковой.

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

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