歸并排序算法的僞代碼和實作

僞代碼

MERGE(A,p,q,r)
    n1=q-p+1;
    n2=r-q;
    create new arrays L[n1+1] and R[n2+1]
    for i=0 to n1-1
        L[i]=A[p+i]
    for j=0 to n2-1
        R[j]=A[q+1+j]
    L[n1]=1000//假設1000是無窮大
    R[n2]=1000
    i=j=0
    for k=p to r
        if(L[i]<=R[j])
            A[k]=L[i]
            i=i+1
        else
            A[k]=R[j]
            j=j+1
MERGE_SORT(A,p,r)
    if p<r
        q=floor((p+r)/2)
        MERGE_SORT(A,p,q)
        MERGE_SORT(A,q+1,r)
        MERGE(A,p,q,r)
           

c實作

void main(){
    int A[]={,,,,,,,};
    int i;
    int len=sizeof(A)/sizeof(A[]);
    merge_sort(A,,);
    for(i=;i<len;i++){
        printf("%d ",A[i]);
    }
}
void merge(int A[],int p,int q,int r){
    int n1,n2,i,j,k;
    n1=q-p+;
    n2=r-q;
    int L[n1+];
    int R[n2+];
    for(i=;i<n1;i++){
        L[i]=A[p+i];
    }
    for(j=;j<n2;j++){
        R[j]=A[q+j+];
    }
    L[n1]=;//假設100是無窮大的數
    R[n2]=;
    i=;
    j=;
    for(k=p;k<=r;k++){
        if(L[i]<=R[j]){
            A[k]=L[i];
            i=i+;
        }else{
            A[k]=R[j];
            j=j+;
        }
    }
}
void merge_sort(int A[],int p,int r){
    int q;
    if(p<r){
        q=floor((p+r)/);
        merge_sort(A,p,q);
        merge_sort(A,q+,r);
        merge(A,p,q,r);
    }
}
           

java實作

public class Main {

    public static void main(String[] args) {
        int [] arr={,,,,,,,};
        merge_sort(arr,,);
        for(int i=;i<arr.length;i++)
            System.out.print(arr[i]+" ");
    }
    public static void merge(int [] arr,int p,int q,int r){
        int len1=q-p+;
        int len2=r-q;
        int [] arrLeft=new int[len1+];
        int [] arrRight=new int[len2+];
        for(int i=;i<len1;i++){
            arrLeft[i]=arr[p+i];
        }
        for(int j=;j<len2;j++){
            arrRight[j]=arr[q++j];
        }
        arrLeft[len1]=;
        arrRight[len2]=;
        int i=;
        int j=;
        for(int k=p;k<=r;k++){
            if(arrLeft[i]<=arrRight[j]){
                arr[k]=arrLeft[i];
                i++;
            }else{
                arr[k]=arrRight[j];
                j++;
            }
        }
    }
    public static void merge_sort(int [] arr,int p,int r){
        if(p<r){
            int q=(int)Math.floor((p+r)/);
            merge_sort(arr,p,q);
            merge_sort(arr,q+,r);
            merge(arr,p,q,r);
        }
    }
}