如何迭代编写合并排序？

Question

我写过一个合并排序的递归版本。它使用一个单独的merge常规的：

def merge(lst1, lst2): 
    i = j = 0 
    merged = [] 
    while i < len(lst1) and j < len(lst2): 
     if lst1[i] <= lst2[j]: 
      merged.append(lst1[i]) 
      i += 1 
     else: 
      merged.append(lst2[j]) 
      j += 1 
    merged.extend(lst1[i:]) 
    merged.extend(lst2[j:]) 
    return merged 

def merge_sort(lst): 
    if len(lst) < 2: 
     return lst 
    else: 
     middle = len(lst)/2 
     return merge(merge_sort(lst[:middle]), merge_sort(lst[middle:])) 

为了节省堆栈空间（和踢/学习算法的纯粹的快乐），我想在一个迭代的方式来写这个功能。但是，我觉得这很难，因为我不知道如何在最终结合不同的列表。

谢谢！

Answer 1

您将需要一个merge函数（相同或几乎相同的merge函数），它将被重复调用。所以，你不需要改变merge函数。

这是一个多通道解决方案。以块大小2开始，并在每次传递中将块大小加倍。

在每一遍中，将列表分成不重叠的大小不等的块。将每个块拆分为2部分，并在2部分上调用merge。

这是自下而上的版本。

Answer 2

我根据Divya的描述进行了扩展（添加了验证测试功能）。下面的代码可以通过消除子数组（data_1和data_2）并进行排序来优化。

def merge_sort_iterative(data): 
    """ gets the data using merge sort and returns sorted.""" 

    for j in range(1, len(data)): 
    j *= 2 
    for i in range(0,len(data),j): 
     data_1 = data[i:i+(j/2)] 
     data_2 = data[i+(j/2):j-i] 
     l = m = 0 
     while l < len(data_1) and m < len(data_2): 
     if data_1[l] < data_2[m]: 
      m += 1 
     elif data_1[l] > data_2[m]: 
      data_1[l], data_2[m] = data_2[m], data_1[l] 
      l += 1 
     data[i:i+(j/2)], data[i+(j/2):j-i] = data_1, data_2 

    return data 

def test_merge_sort(): 
    """test function for verifying algorithm correctness""" 

    import random 
    import time 

    sample_size = 5000 
    sample_data = random.sample(range(sample_size*5), sample_size) 
    print 'Sample size: ', sample_size 

    begin = time.time() 
    sample_data = [5,4,3,2,1] 
    result = merge_sort_iterative(sample_data) 
    end = time.time() 
    expected = sorted(sample_data) 
    print 'Sorting time: %f \'secs'%(end-begin) 

    assert result == expected, 'Algorithm failed' 
    print 'Algorithm correct' 

if __name__ == '__main__': 
    test_merge_sort() 

Answer 3

这里是Java实现

public static <T extends Comparable<? super T>> void iterativeMergeSort(T[] seed) { 

    for (int i = 1; i <seed.length; i=i+i) 
    { 
     for (int j = 0; j < seed.length - i; j = j + i+i) 
     { 
      inPlaceMerge(seed, j, j + i-1, Math.min(j+i + i -1, seed.length -1)); 
     } 
    }  
} 

public static <T extends Comparable<? super T>> void inPlaceMerge(T[] collection, int low, int mid, int high) { 
    int left = low; 
    int right = mid + 1; 

    if(collection[mid].equals(collection[right])) { 
     return ;//Skip the merge if required 
    } 
    while (left <= mid && right <= high) {   
     // Select from left: no change, just advance left 
     if (collection[left].compareTo(collection[right]) <= 0) { 
      left ++; 
     } else { // Select from right: rotate [left..right] and correct 
      T tmp = collection[right]; // Will move to [left] 
      rotateRight(collection, left, right - left); 
      collection[left] = tmp; 
      // EVERYTHING has moved up by one 
      left ++; right ++; mid ++; 
     } 
    }  
} 

这里是单元测试

private Integer[] seed; 

@Before 
public void doBeforeEachTestCase() { 
    this.seed = new Integer[]{4,2,3,1,5,8,7,6}; 
} 
@Test 
public void iterativeMergeSortFirstTest() { 
    ArrayUtils.<Integer>iterativeMergeSort(seed); 
    Integer[] result = new Integer[]{1,2,3,4,5,6,7,8}; 
    assertThat(seed, equalTo(result)); 
} 

Answer 4

递归是更直观，因此我更喜欢相同，除了在某些情况下，当我想避免显着的堆栈深度（例如，当消费某些协同例程实现时）。在合并排序的情况下，迭代版本实际上更容易遵循（至少是伪代码）。

所有需要的是一个嵌套循环，内部循环在2^k元素对上执行合并，外部循环负责增加k。

需要执行的其他步骤是将任何未配对的组与以前的合并组合并。如果元素的数量不是2的幂，则会遇到未配对的组。未配对的组将始终处于迭代结束时。

例如[5,7] [3,4] [1,9] - > [3,4,5,7] [1,9] - > [5,7] [3，4，9] - > [5,7] 1,3,4,5,7,9]

在上面的例子中[1，9]是一个组没有另一个组最初被合并。因此，它被合并与前一组（其中进行了合并和排序的话）

这里是一个Python实现：

from MergeSort import merge 

def sort(arr): 
    n = len(arr) - 1 
    c = 1 
    start = 0 
    mid = 0 
    end = 0 
    while c <= n: 
     while end < n: 
      mid = start + c//2 
      end = start + c 
      if (start < n) and (end <= n): 
       merge(arr, start, mid, end) 
       start = end + 1 
      else: 
       merge(arr, start - c - 1, start-1, n) 
     c = 2*c + 1 
     start = 0 
     mid = 0 
     end = 0 

我从普通（递归）版本使用的合并功能。虽然上面的代码并不是最优雅的，但它的工作原理和复杂度与递归版本相同。（我还没有彻底检查，但它从一个快速的一瞥，似乎这样对我）

这是一个单元测试：

def test_merge_sort_iterative(self): 
    for i in range(1, 100): 
     length = randint(10, 5000) 
     data = [randint(1, 10000) for x in range(1, length)] 
     IterativeMergeSort.sort(data) 
     issorted = True 
     i = 0 
     while (i < len(data) - 1) & issorted: 
      if data[i] > data[i + 1]: 
       issorted = False 
      i += 1 
    self.assertTrue(issorted, data) 
    return