合并算法的核心操作就是將一維數(shù)組中前后相鄰的兩個(gè)兩個(gè)有序序列合并成一個(gè)有序序列。合并算法也可以采用遞歸算法來實(shí)現(xiàn),形式上較為簡單,但實(shí)用性很差。

合并算法的合并次數(shù)是一個(gè)非常重要的量,根據(jù)計(jì)算當(dāng)數(shù)組中有3到4個(gè)元素時(shí),合并次數(shù)是2次,當(dāng)有5到8個(gè)元素時(shí),合并次數(shù)是3次,當(dāng)有9到16個(gè)元素時(shí),合并次數(shù)是4次,按照這一規(guī)律,當(dāng)有N個(gè)子序列時(shí)可以推斷出合并的次數(shù)是X(2 >=N,符合此條件的最小那個(gè)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;