合并算法的核心操作就是将一维数组中前后相邻的两个两个有序序列合并成一个有序序列。合并算法也可以采用递归算法来实现,形式上较为简单,但实用性很差。

合并算法的合并次数是一个非常重要的量,根据计算当数组中有3到4个元素时,合并次数是2次,当有5到8个元素时,合并次数是3次,当有9到16个元素时,合并次数是4次,按照这一规律,当有N个子序列时可以推断出合并的次数是X(2 >=N,符合此条件的最小那个X)。

源程序:

 

program hebing;

const

 n=10;

var

 a:array[1..n] of integer;

 i:integer;

 

procedure init;

 var

    i:integer;

 begin

    for i:=1 to n do read(a[i]);

    readln;

 end;

 

procedure merge(low,mid,high:integer);

 var

    h,i,j,k:integer;

    b:array[1..n] of integer;

 

 begin

    h:=low; i:=low; j:=mid+1;

    while (h<=mid) and (j<=high) do

      begin

        if (a[h]<=a[j]) then

          begin

            b[i]:=a[h]; h:=h+1;

          end

        else

          begin

            b[i]:=a[j]; j:=j+1;

          end;

        i:=i+1;

      end;

    if h>mid then

      for k:=j to high do

        begin

          b[i]:=a[k]; i:=i+1;

        end

    else

      for k:=h to mid do

        begin

          b[i]:=a[k]; i:=i+1;

        end;

    for k:=low to high do

      a[k]:=b[k];

 end;

 

procedure mergesort(low,high:integer);

 var

    mid:integer;

 begin

    if low<high then

       begin

         mid:=(low+high) div 2;

         mergesort(low,mid);

         mergesort(mid+1,high);

         merge(low,mid,high);

       end;

 end;