有没有一种非递归的方法将每个列表元素分隔成各自的列表？

Question

我在看维基百科的伪代码（以及其他类似的网页sortvis.org网站和分类-算法网)关于merge sort和saw的准备使用递归。
我很好奇是否有一种非递归的方法来实现这一点。
也许像for each i element in list, i=[i-th element]。在

我的印象是递归是最小化的，因为它不受欢迎，因此我想到了这个问题。在

以下是来自Wikipedia的merge sort递归部分的伪代码示例：

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

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

列表切片效果很好。在

Answer 2

Bottom-up merge sort是merge sort的非递归变量。在

有关更详细的伪代码实现，请参见wikipedia page。在

Answer 3

作为旁白-递归本身并不是不受欢迎的。在

如果堆栈空间有限，递归是不可取的（您是否害怕stackoverflow？；—）），或者在某些情况下，函数调用的时间开销非常重要。在

在大多数情况下，这些条件并不成立；代码的可读性和可维护性将更加相关。在我看来，像merge-sort这样的算法在递归表达时更有意义。在