合并排序的伪代码如何工作？ [英] How does the Pseudocode for merge sort work?

问题描述

我已经获得了用于合并排序的伪代码。但是还不清楚它是如何工作的。有人可以向我解释吗？

I have got this Pseudocode for merge sort. But not really clear how it works. can anyone please explain to me?

for i=1 ; i<size ; i=2i
   for j=0 ; j<size - i ; j= j+2i
     Merge(&A[j] , i , min(2i,size-j))

Merge（）方法是：

And the Merge() method is:

Merge(A, end1, end2)
  i = 0; j = end1 ; k =0

while i<end1 and j<end2
  if(A[i] < A[j])
    temp[k] = A[i]
  else
     temp[k] = A[j]
     j = j+1, k=k+1

while i<end1
   temp[k] = A[i]
   i = i+1 , k=k+1

while j<end2
   temp[k] = A[j]
   j = j+1 , k=k+1

for(i=0 ; i<end2; i++)
    A[i] = temp[i]

来源：
http://www.youtube.com/watch?v=GCae1WNvnZM&list=PL89B61F78B552C1AB&index=4

如果有人可以给我更好的算法教程资料，那真是太棒了..
预先感谢。 ：-）

if anyone can give me better source for algorithm tutorials, that wud be awsome too.. Thanks in advance. :-)

推荐答案

让我们从合并操作开始：它将两个连续存储的序列作为输入。该函数将两个序列中的所有元素都复制到临时存储中，始终选择这两个序列中的最小元素（当两个序列中的任何一个都用尽时，复制将继续另一个序列）。然后将所有元素复制回原始存储。

Let us start with the merge operation: it takes as input two sequences that are stored contiguously. The function copies to temporary storage all the elements from both sequences, always choosing the smallest of the two (when either sequence is exhausted, the copy continues with the other sequence). Then all elements are copied back to the original storage.

如果您承认两个输入序列是按排序顺序提供的，则合并的结果就是一个单独的排序序列

If you admit that the two input sequences are provided in sorted order, the result of the merge is a single sorted sequence.

现在是主程序。它由两个嵌套循环组成。外部的监视器监视序列的长度（从1开始），并每次将其加倍。内部循环一次获取两个序列，计算它们的存储位置，然后将它们合并为一个。

Now the main program. It is formed of two nested loops. The outer one monitors the length of the sequences, starting from 1, and doubles it every time. The inner loop takes two sequences at a time, computing where they are stored, and merges them into a single.

MergeSort的神奇之处在于：最初，所有元素形成1个元素的序列，这些序列显然已排序。一遍（内部循环）后，您将获得2个元素的排序序列。然后是4 ...直到剩下单个排序的序列。

And here comes the magic of MergeSort: initially, all elements form sequences of 1 element, which are obviously sorted. After one pass (the inner loop), you get sorted sequences of 2 elements. Then of 4... until there remains a single sorted sequence.

|e|b|g|h|c|a|f|d|
|be|gh|ac|df|
|begh|acdf|
|abcdefgh|

这篇关于合并排序的伪代码如何工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！