我知道合并排序的工作原理，但是合并排序代码的工作原理是什么? [英] I know how Merge Sort works, but How Merge Sort Code Works?

问题描述

您可以在Wikipedia上阅读此内容:

You can read this on Wikipedia:

function merge_sort(list m)
// Base case. A list of zero or one elements is sorted, by definition.
if length(m) <= 1
    return m

// Recursive case. First, *divide* the list into equal-sized sublists.
var list left, right
var integer middle = length(m) / 2
for each x in m before middle
     add x to left
for each x in m after or equal middle
     add x to right

// Recursively sort both sublists
left = merge_sort(left)
right = merge_sort(right)

// Then merge the now-sorted sublists.
return merge(left, right)

第1行有一个数字列表，比方说9 6 3 7 5 1 8 2

On line 1 there's a list of numbers, let's say 9 6 3 7 5 1 8 2

他们说merge_sort一次又一次地将列表分为2和2，直到每个列表只剩下1个整数，就像这样:

They say that merge_sort divides the list on 2 and 2 again and again until each list has only 1 integer left, like this one:

9 6 3 7 5 1 8 2 -->
9 6 3 7 - 5 1 8 2 -->
9 6 - 3 7 - 5 1 - 8 2 -->
9 - 6 - 3 - 7 - 5 - 1 - 8 - 2

然后将数字像这样放在一起:

And then the numbers are put together like this:

6 9 - 3 7 - 1 5 - 2 8 -->
3 6 7 9 - 1 2 5 8 -->
1 2 3 5 6 7 8 9 -->

但是我看不到整数在列表中何处一次又一次地除以2，直到每个仅剩1个整数了?

var list left, right
var integer middle = length(m) / 2
for each x in m before middle
     add x to left
for each x in m after or equal middle
     add x to right

据我了解，在上面的代码中，数字列表分为两个不同的列表:9 6 3 7和5 1 8 2

As I understand, on the code above, the list of numbers is divided to two different lists: 9 6 3 7 and 5 1 8 2

下面的代码会发生什么?

left = merge_sort(left)
right = merge_sort(right)

有人可以向我解释上面的merge_sort代码是如何逐步正确运行的吗?

推荐答案

伪代码缺少一些细节.讨论页面上有关于删除或修复它的辩论.请注意，它应该使用列表而不是数组，这就是为什么元素一次只能追加一个的原因.该列表并没有真正分成两部分；而是创建两个新的最初为空的列表 left 和 right ，然后将(middle = length/2)元素从 list 移至左侧，然后将(长度-中间)元素从 list 移至 right .这个带有C ++注释的清理示例可能更有意义，但是它仍然不是一种有效的列表排序方式.使用指针数组进行自下而上的合并排序效率更高.如果有人感兴趣，我可以在此处添加示例代码.

The pseudo code is missing some details. There was debate on the talk page about removing it or fixing it. Note it's supposed to be working with a list, not an array, which is why elements can only be appended one at a time. The list is not really split into 2 parts; instead two new initially empty lists left and right are created, then (middle = length/2) elements are moved from list to left, then (length - middle) elements are moved from list to right. This cleaned up example with C++ comments may make more sense, but it's still an inefficient way to sort a list. A bottom up merge sort using an array of pointers is much more efficient. I can add example code here if anyone is interested.

var list left, right
var integer middle = length(m) / 2
var integer count
for (count = 0; count < middle; count += 1)
     get x from front of list        // x = *list.front()
     remove first element from list  // list.pop_front()
     add x to left                   // left.push_back(x)
for (count = middle; count < length; count += 1)
     get x from front of list        // x = *list.front()
     remove first element from list  // list.pop_front()
     add x to right                  // right.push_back(x)

在同一wiki文章中，有两个类似C/C ++的代码示例，应该更容易理解.这些示例经过了简化，并在每个合并步骤之后将数据复制回原始阵列，这可以通过更优化的代码来避免.

In that same wiki article, there are two C / C++ like code examples, which should be easier to understand. The examples are simplified and copy data back to the original array after each merge step, which could be avoided with more optimized code.

http://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation

http://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation

自顶向下合并排序的顺序有所不同，先深度，先左:

The sequence is different for top down merge sort, it's depth first, left first:

9 6 3 7 5 1 8 2
9 6 3 7|5 1 8 2
9 6|3 7
9|6
6 9
    3|7
    3 7
3 6 7 9
        5 1|8 2
        5|1
        1 5
            8|2
            2 8
        1 2 5 8
1 2 3 5 6 7 8 9

自下而上的合并排序将跳过递归操作，并假设运行大小为1，然后从左至右首先合并宽度.

Bottom up merge sort skips the recursion and just starts off assuming a run size of 1, and merges width first, left to right:

9 6 3 7 5 1 8 2
9|6|3|7|5|1|8|2           run size = 1
6 9|3 7|1 5|2 8           run size = 2
3 6 7 9|1 2 5 8           run size = 4
1 2 3 5 6 7 8 9           done

自底向上合并排序算法的另一个示例:

Another example of bottom up merge sort algorithm:

http://www.mathcs.emory.edu/〜cheung/Courses/171/Syllabus/7-Sort/merge-sort5.html

这篇关于我知道合并排序的工作原理，但是合并排序代码的工作原理是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！