二路歸並排序java實現

A. java怎麼實現排序

Java實現幾種常見排序方法

日常操作中常見的排序方法有：冒泡排序、快速排序、選擇排序、插入排序、希爾排序，甚至還有基數排序、雞尾酒排序、桶排序、鴿巢排序、歸並排序等。
以下常見演算法的定義
1. 插入排序：插入排序基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，演算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。插入排序的基本思想是：每步將一個待排序的紀錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。
2. 選擇排序：選擇排序（Selection sort）是一種簡單直觀的排序演算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。 選擇排序是不穩定的排序方法。
3. 冒泡排序：冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序演算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越大的元素會經由交換慢慢「浮」到數列的頂端。
4. 快速排序：快速排序（Quicksort）是對冒泡排序的一種改進。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
5. 歸並排序：歸並排序是建立在歸並操作上的一種有效的排序演算法,該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並。
6. 希爾排序：希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法便終止。
https://www.cnblogs.com/wangmingshun/p/5635292.html

B. JAVA中有哪幾種常用的排序方法每個排序方法的實現思路是如何的每個方法的思想是什麼

一、冒泡排序

已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先比較 a[1]與a[2]的值，若a[1]大於a[2]則交換兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大於a[3]則交換兩者的值，否則不變。再比較a[3]與a[4]，以此類推，最後比較a[n-1]與a[n]的值。這樣處理一輪後，a[n]的值一定是這組數據中最大的。再對 a[1]~a[n-1]以相同方法處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理一輪，以此類推。共處理n-1輪後a[1]、a[2]、……a[n]就以升序排列了。

優點：穩定；

缺點：慢，每次只能移動相鄰兩個數據。

二、選擇排序

冒泡排序的改進版。

每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數據元素排完。

選擇排序是不穩定的排序方法。

n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：

①初始狀態：無序區為R[1..n]，有序區為空。

②第1趟排序

在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。

……

③第i趟排序

第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(1≤i≤n- 1)。該趟排序從當前無序區中選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。

這樣，n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。

優點：移動數據的次數已知（n-1次）；

缺點：比較次數多。

三、插入排序

已知一組升序排列數據a[1]、a[2]、……a[n]，一組無序數據b[1]、 b[2]、……b[m]，需將二者合並成一個升序數列。首先比較b[1]與a[1]的值，若b[1]大於a[1]，則跳過，比較b[1]與a[2]的值，若b[1]仍然大於a[2]，則繼續跳過，直到b[1]小於a數組中某一數據a[x]，則將a[x]~a[n]分別向後移動一位，將b[1]插入到原來 a[x]的位置這就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若無數組a，可將b[1]當作n=1的數組a）

優點：穩定，快；

缺點：比較次數不一定，比較次數越少，插入點後的數據移動越多，特別是當數據總量龐大的時候，但用鏈表可以解決這個問題。

三、縮小增量排序

由希爾在1959年提出，又稱希爾排序(shell排序)。

已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。發現當n不大時，插入排序的效果很好。首先取一增量d(d<n)，將a[1]、a[1+d]、a[1+2d]……列為第一組，a[2]、a[2+d]、 a[2+2d]……列為第二組……，a[d]、a[2d]、a[3d]……列為最後一組以次類推，在各組內用插入排序，然後取d'<d，重復上述操作，直到d=1。

優點：快，數據移動少；

缺點：不穩定，d的取值是多少，應取多少個不同的值，都無法確切知道，只能憑經驗來取。

四、快速排序

快速排序是目前已知的最快的排序方法。

已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先任取數據 a[x]作為基準。比較a[x]與其它數據並排序，使a[x]排在數據的第k位，並且使a[1]~a[k-1]中的每一個數據<a[x]，a[k+1]~a[n]中的每一個數據>a[x]，然後採用分治的策略分別對a[1]~a[k-1]和a[k+1]~a[n] 兩組數據進行快速排序。

優點：極快，數據移動少；

缺點：不穩定。

五、箱排序

已知一組無序正整數數據a[1]、a[2]、……a[n]，需將其按升序排列。首先定義一個數組x[m],且m>=a[1]、a[2]、……a[n]，接著循環n次，每次x[a]++.

優點：快，效率達到O(1)

缺點：數據范圍必須為正整數並且比較小

六、歸並排序

歸並排序是多次將兩個或兩個以上的有序表合並成一個新的有序表。最簡單的歸並是直接將兩個有序的子表合並成一個有序的表。

歸並排序是穩定的排序.即相等的元素的順序不會改變.如輸入記錄 1(1) 3(2) 2(3) 2(4) 5(5) (括弧中是記錄的關鍵字)時輸出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按輸入的順序.這對要排序數據包含多個信息而要按其中的某一個信息排序,要求其它信息盡量按輸入的順序排列時很重要.這也是它比快速排序優勢的地方.

C. 歸並排序的示例代碼

歸並排序原理
歸並排序具體工作原理如下（假設序列共有n個元素）：
將序列每相鄰兩個數字進行歸並操作（merge)，形成floor(n/2)個序列，排序後每個序列包含兩個元素
將上述序列再次歸並，形成floor(n/4)個序列，每個序列包含四個元素
重復步驟2，直到所有元素排序完畢
示例代碼
Go語言 funcmergeSort(r[]int)[]int{length:=len(r)iflength<=1{returnr}num:=length/2left:=mergeSort(r[:num])right:=mergeSort(r[num:])returnmerge(left,right)}funcmerge(left,right[]int)(result[]int){l,r:=0,0forl<len(left)&&r<len(right){ifleft[l]<right[r]{result=append(result,left[l])l++}else{result=append(result,right[r])r++}}result=append(result,left[l:]...)result=append(result,right[r:]...)return}Java語言 packagealgorithm;publicclassMergeSort{//privatestaticlongsum=0;/***<pre>*二路歸並*原理：將兩個有序表合並和一個有序表*</pre>**@parama*@params*第一個有序表的起始下標*@paramm*第二個有序表的起始下標*@paramt*第二個有序表的結束小標**/privatestaticvoidmerge(int[]a,ints,intm,intt){int[]tmp=newint[t-s+1];inti=s,j=m,k=0;while(i<m&&j<=t){if(a[i]<=a[j]){tmp[k]=a[i];k++;i++;}else{tmp[k]=a[j];j++;k++;}}while(i<m){tmp[k]=a[i];i++;k++;}while(j<=t){tmp[k]=a[j];j++;k++;}System.array(tmp,0,a,s,tmp.length);}/****@parama*@params*@paramlen*每次歸並的有序集合的長度*/publicstaticvoidmergeSort(int[]a,ints,intlen){intsize=a.length;intmid=size/(len<<1);intc=size&((len<<1)-1);//-------歸並到只剩一個有序集合的時候結束演算法-------//if(mid==0)return;//------進行一趟歸並排序-------//for(inti=0;i<mid;++i){s=i*2*len;merge(a,s,s+len,(len<<1)+s-1);}//-------將剩下的數和倒數一個有序集合歸並-------//if(c!=0)merge(a,size-c-2*len,size-c,size-1);//-------遞歸執行下一趟歸並排序------//mergeSort(a,0,2*len);}publicstaticvoidmain(String[]args){int[]a=newint[]{4,3,6,1,2,5};mergeSort(a,0,1);for(inti=0;i<a.length;++i){System.out.print(a[i]+);}}}Python語言 defMergeSort(lists):iflen(lists)<=1:returnlistsnum=int(len(lists)/2)left=MergeSort(lists[:num])right=MergeSort(lists[num:])returnMerge(left,right)defMerge(left,right):r,l=0,0result=[]whilel<len(left)andr<len(right):ifleft[l]<right[r]:result.append(left[l])l+=1else:result.append(right[r])r+=1result+=right[r:]result+=left[l:]returnresultprintMergeSort([1,2,3,4,5,6,7,90,21,23,45])C語言 #include<stdlib.h>#include<stdio.h>voidMerge(intsourceArr[],inttempArr[],intstartIndex,intmidIndex,intendIndex){inti=startIndex,j=midIndex+1,k=startIndex;while(i!=midIndex+1&&j!=endIndex+1){if(sourceArr[i]>=sourceArr[j])tempArr[k++]=sourceArr[j++];elsetempArr[k++]=sourceArr[i++];}while(i!=midIndex+1)tempArr[k++]=sourceArr[i++];while(j!=endIndex+1)tempArr[k++]=sourceArr[j++];for(i=startIndex;i<=endIndex;i++)sourceArr[i]=tempArr[i];}//內部使用遞歸voidMergeSort(intsourceArr[],inttempArr[],intstartIndex,intendIndex){intmidIndex;if(startIndex<endIndex){midIndex=(startIndex+endIndex)/2;MergeSort(sourceArr,tempArr,startIndex,midIndex);MergeSort(sourceArr,tempArr,midIndex+1,endIndex);Merge(sourceArr,tempArr,startIndex,midIndex,endIndex);}}intmain(intargc,char*argv[]){inta[8]={50,10,20,30,70,40,80,60};inti,b[8];MergeSort(a,b,0,7);for(i=0;i<8;i++)printf(%d,a[i]);printf( );return0;}PHP語言 //merge函數將指定的兩個有序數組(arr1arr2,)合並並且排序//我們可以找到第三個數組,然後依次從兩個數組的開始取數據哪個數據小就先取哪個的,然後刪除掉剛剛取過///的數據functional_merge($arrA,$arrB){$arrC=array();while(count($arrA)&&count($arrB)){//這里不斷的判斷哪個值小,就將小的值給到arrC,但是到最後肯定要剩下幾個值,//不是剩下arrA裡面的就是剩下arrB裡面的而且這幾個有序的值,肯定比arrC裡面所有的值都大所以使用$arrC[]=$arrA['0']<$arrB['0']?array_shift($arrA):array_shift($arrB);}returnarray_merge($arrC,$arrA,$arrB);}//歸並排序主程序functional_merge_sort($arr){$len=count($arr);if($len<=1)return$arr;//遞歸結束條件,到達這步的時候,數組就只剩下一個元素了,也就是分離了數組$mid=intval($len/2);//取數組中間$left_arr=array_slice($arr,0,$mid);//拆分數組0-mid這部分給左邊left_arr$right_arr=array_slice($arr,$mid);//拆分數組mid-末尾這部分給右邊right_arr$left_arr=al_merge_sort($left_arr);//左邊拆分完後開始遞歸合並往上走$right_arr=al_merge_sort($right_arr);//右邊拆分完畢開始遞歸往上走$arr=al_merge($left_arr,$right_arr);//合並兩個數組,繼續遞歸return$arr;}$arr=array(12,5,4,7,8,3,4,2,6,4,9);print_r(al_merge_sort($arr));Pascal語言 programmergesort_1;constmaxn=7;typearr=array[1..maxn]ofinteger;vara,b,c:arr;i:integer;proceremerge(r:arr;l,m,n:integer;varr2:arr);vari,j,k,p:integer;begini:=l;j:=m+1;k:=l-1;while(i<=m)and(j<=n)dobegink:=k+1;ifr[i]<=r[j]thenbeginr2[k]:=r[i];i:=i+1endelsebeginr2[k]:=r[j];j:=j+1;endend;ifi<=mthenforp:=itomdobegink:=k+1;r2[k]:=r[p];end;ifj<=nthenforp:=jtondobegink:=k+1;r2[k]:=r[p];end;end;proceremergesort(varr,r1:arr;s,t:integer);vark:integer;c:arr;beginifs=tthenr1[s]:=r[s]elsebegink:=(s+t)div2;mergesort(r,c,s,k);mergesort(r,c,k+1,t);merge(c,s,k,t,r1)end;end;beginwrite('Enterdata:');fori:=1tomaxndoread(a[i]);mergesort(a,b,1,maxn);fori:=1tomaxndowrite(b[i]:9);writeln;end.//============================================programmergesort_2;constmax=100000;vara,r:array[1..max]oflongint;n,i:longint;proceremsort(s,t:longint);varm,i,j,k:longint;beginifs=tthenexit;m:=(s+t)div2;msort(s,m);msort(m+1,t);i:=s;j:=m+1;k:=s;while(i<=m)and(j<=t)dobeginifa[i]<a[j]thenbeginr[k]:=a[i];inc(i);inc(k);endelsebeginr[k]:=a[j];inc(j);inc(k);end;end;whilei<=mdobeginr[k]:=a[i];inc(i);inc(k);end;whilej<=tdobeginr[k]:=a[j];inc(j);inc(k);end;fori:=stotdoa[i]:=r[i];end;beginreadln(n);fori:=1tondoread(a[i]);msort(1,n);fori:=1tondowriteln(a[i]);end.Basic語言 SubMergeSort(Array()AsInteger,FirstAsInteger,LastAsInteger)DimmidAsInteger=0Iffirst<lastThenmid=(first+last)2MergeSort(Array,first,mid);MergeSort(Array,mid+1,last);Merge(Array,first,mid,last);EndIfEndSub/*以下示例代碼實現了歸並操作。array[]是元素序列，其中從索引p開始到q位置，按照升序排列，同時，從(q+1)到r也已經按照升序排列，merge()函數將把這兩個已經排序好的子序列合並成一個排序序列。結果放到array中。*//***0<=p<=q<r,subarrayarray[p..q]andarray[q+1..r]arealreadysorted.*themerge()functionmergesthetwosub-arraysintoonesortedarray.*/voidMerge(intarray[],intp,intq,intr){inti,k;intbegin1,end1,begin2,end2;int*temp=(int*)malloc((r-p+1)*sizeof(int));begin1=p;end1=q;begin2=q+1;end2=r;k=0;while((begin1<=end1)&&(begin2<=end2)){if(array[begin1]<=array[begin2]){temp[k]=array[begin1];begin1++;}else{temp[k]=array[begin2];begin2++;}k++;}while(begin1<=end1||begin2<=end2){if(begin1<=end1){temp[k++]=array[begin1++];}if(begin2<=end2){temp[k++]=array[begin2++];}}for(i=0;i<=(r-p);i++)array[p+i]=temp[i];free(temp);}JavaScript語言
使用遞歸的代碼如下。優點是描述演算法過程思路清晰，缺點是使用遞歸，mergeSort()函數頻繁地自我調用。長度為n的數組最終會調用mergeSort()函數 2n-1次，這意味著一個長度超過1500的數組會在Firefox上發生棧溢出錯誤。可以考慮使用迭代來實現同樣的功能。 functionmerge(left,right){varresult=[];while(left.length>0&&right.length>0){if(left[0]<right[0]){/*shift()方法用於把數組的第一個元素從其中刪除，並返回第一個元素的值。*/result.push(left.shift());}else{result.push(right.shift());}}returnresult.concat(left).concat(right);}functionmergeSort(items){if(items.length==1){returnitems;}varmiddle=Math.floor(items.length/2),left=items.slice(0,middle),right=items.slice(middle);returnmerge(mergeSort(left),mergeSort(right));}非遞歸演算法（C++） #include<iostream>#include<ctime>#include<cstring>#include<cstdlib>usingnamespacestd;/**將a開頭的長為length的數組和b開頭長為right的數組合並n為數組長度，用於最後一組*/voidMerge(int*data,inta,intb,intlength,intn){intright;if(b+length-1>=n-1)right=n-b;elseright=length;int*temp=newint[length+right];inti=0,j=0;while(i<=length-1&&j<=right-1){if(data[a+i]<=data[b+j]){temp[i+j]=data[a+i];i++;}else{temp[i+j]=data[b+j];j++;}}if(j==right){//a中還有元素，且全都比b中的大,a[i]還未使用memcpy(temp+i+j,data+a+i,(length-i)*sizeof(int));}elseif(i==length){memcpy(temp+i+j,data+b+j,(right-j)*sizeof(int));}memcpy(data+a,temp,(right+length)*sizeof(int));delete[]temp;}voidMergeSort(int*data,intn){intstep=1;while(step<n){for(inti=0;i<=n-step-1;i+=2*step)Merge(data,i,i+step,step,n);//將i和i+step這兩個有序序列進行合並//序列長度為step//當i以後的長度小於或者等於step時，退出step*=2;//在按某一步長歸並序列之後，步長加倍}}intmain(){intn;cin>>n;int*data=newint[n];if(!data)exit(1);intk=n;while(k--){cin>>data[n-k-1];}clock_ts=clock();MergeSort(data,n);clock_te=clock();k=n;while(k--){cout<<data[n-k-1]<<'';}cout<<endl;cout<<thealgorithmused<<e-s<<miliseconds.<<endl;deletedata;return0;}二路歸並
ConstFI='in.txt';FO='out.txt';MaxN=10000;TypeTIndex=Longint;TDat=Array[0..MaxN]OfTIndex;VarN:TIndex;Dat:TDat;Tmp:TDat;ProcereMerge(L,Mid,R:TIndex);VarP1,P2:TIndex;E1,E2:TIndex;P:TIndex;I:TIndex;BeginP1:=L;P2:=Mid+1;P:=L;RepeatIf(Dat[P1]<=Dat[P2])ThenBeginTmp[P]:=Dat[P1];Inc(P1);Inc(P);EndElseBeginTmp[P]:=Dat[P2];Inc(P2);Inc(P);End;Until(P1=Mid+1)Or(P2=R+1);If(P1=Mid+1)ThenBeginE1:=P2;E2:=R;EndElseBeginE1:=P1;E2:=Mid;End;ForI:=E1ToE2DoBeginTmp[P]:=Dat[I];Inc(P);End;End;ProcereSort(L,R:TIndex);VarMid:TIndex=0;BeginMid:=(L+R)Shr1;If(L<Mid)ThenSort(L,Mid);If(Mid+1<R)ThenSort(Mid+1,R);Merge(L,Mid,R);ForMid:=LToRDoDat[Mid]:=Tmp[Mid];End;ProcereInit;VarI:TIndex;BeginFillChar(Dat,SizeOf(Dat),0);Readln(N);ForI:=1ToNDoRead(Dat[I]);End;ProcereMain;BeginSort(1,N);End;ProcereFinal;VarI:TIndex;BeginForI:=1ToNDoWrite(Dat[I],'');Writeln;End;BeginAssign(Input,FI);Assign(Output,FO);Reset(Input);Rewrite(Output);Init;Main;Final;Close(Input);Close(Output);End.
Delphi歸並排序完整源代碼例子： //合並子函數procereTForm1.MergePass(vardatas:arrayofInteger;left,mid,right:Integer);vartmpArr:arrayofInteger;arrLen:Integer;i,k:Integer;begin1,begin2,end1,end2:Integer;beginarrLen:=right-left+1;SetLength(tmpArr,arrLen);begin1:=left;end1:=mid;begin2:=mid+1;end2:=right;k:=0;while((begin1<=end1)and(begin2<=end2))dobeginif(datas[begin1]<datas[begin2])thenbegintmpArr[k]:=datas[begin1];Inc(begin1);endelsebegintmpArr[k]:=datas[begin2];Inc(begin2);end;inc(k);end;while(begin1<=end1)dobegintmpArr[k]:=datas[begin1];Inc(begin1);Inc(k);end;while(begin2<=end2)dobegintmpArr[k]:=datas[begin2];Inc(begin2);Inc(k);end;fori:=0to(right-left)dobegindatas[left+i]:=tmpArr[i];end;end;//排序主函數，left是數組左下標，0開始。right是數組右下標。procereTForm1.MergeSort(vardatas:arrayofInteger;left,right:Integer);varmid:Integer;i:Integer;beginmid:=0;if(left<right)thenbeginmid:=(right+left)div2;showLog('中間索引：'+inttostr(mid));MergeSort(datas,left,mid);MergeSort(datas,mid+1,right);MergePass(datas,left,mid,right);showLog('--->'+getArrayString(datas));//顯示數組中間狀態end;end;//調用方法：procereTForm1.btn1Click(Sender:TObject);varinArr:array[0..9]ofInteger;beginCopyMemory(@inArr[0],@CTabls[0],SizeOf(Integer)*10);showLog('輸入數據：'+getArrayString(inArr));MergeSort(inArr,0,High(inArr));showLog('輸出數據：'+getArrayString(inArr));end;

D. java實現歸並排序問題

public void mySort(int low,int high){
int lo=low;
int hi=high;
if (lo>=hi) {
return;
}else{
boolean flag=false;
while (lo<hi) {
if (arrs[lo]>arrs[hi]) {
int temp=arrs[lo];
arrs[lo]=arrs[hi];
arrs[hi]=temp;
flag=!flag;
}else{
if (flag) {
lo++;
}else{
hi--;
}
}

}
lo--;
hi++;
mySort(low,lo);
mySort(hi,high);

}
}
這里是復遞歸加二分法制(排序的方法) 希望能幫到你！！望~~點贊

E. Java 合並排序 求程序

網路文庫找了一個http://wenku..com/view/332fd62d453610661ed9f414.html
四、合並排序 1、基本思想
合並排序的基本操作是：首先將待排序序列劃分為兩個長度相等的子序列；然後分別對兩個子序列進行歸並排序，得到兩個有序的子序列；最後將兩個有序的子序列合並成一個有序數列。
MergeSort(A[2*n]) {
divide A[2*n] into A[1,……,n],A[n-1,……,2*n];//劃分 MergeSort(A[1,……,n]);//歸並排序前半個子序列
MergeSort(A[[n-1,……,2*n]);//歸並排序後半個子序列 Merge;//合並 }
2、演算法復雜度分析
合並步的時間復雜度為O(n)。合並排序演算法的時間復雜度為O(nlog2n)。
3、編程實現
public int[] MergeSort(int[] A, int[] tempA, int s, int t){
//如果序列中有一個以上的元素，即s<t則進行排序
if(s < t){
int center = (s + t) / 2;
MergeSort(A, tempA, s, center)
;//歸並排序前半個子序列
MergeSort(A, tempA, center + 1, t);
//歸並排序後半個子序列
Merge(A,tempA, s, center, t);
//合並
}
return tempA;
}

public int[] Merge(int[] A, int[] tempA, int s, int m, int t){ int n = t- s + 1;
//n為數據總個數
int i=s;j=m+1;k=s
while(i <= m&& j <= t){
//取A[i]和A[j]中較小者放入tempA[k]
if(A[i]<=A[j]){
tempA[k++] = A[i++]; }
else{
tempA[k++] = A[j++]; } }
if(i<=m) while(i<=m)
tempA[k++]=A[i++];//處理前一個子序列
else while(j<=t)
tempA[k++]=A[j++];//處理後一個子序列
return tempA;
}