归并排序-java实现

import java.util.Scanner;

public class TangRongjie {
    //两个有序数组的合并算法，将numb和numc合并到numa，并保持numa有序
    public static int[] merge(int[] numb, int[] numc, int[] numa) {
        //获取numb和numc的长度
        int p = numb.length;
        int q = numc.length;
        //三个数组的循环下标
        int i = 0, j = 0, k = 0;
        //当numb与numc中有一个结束时退出循环
        while(i < p && j < q) {
            //每次比较将较小的数装入numa
            if(numb[i] <= numc[j]) {
                numa[k] = numb[i];
                i = i + 1;
            }
            else {
                numa[k] = numc[j];
                j = j + 1;
            }
            k = k + 1;
        }
        //如果一个数组还有多的部分，将其依次装入numa中
        if(i == p)
            System.arraycopy(numc, j, numa, k, q - j);
        else
            System.arraycopy(numb, i, numa, k, p - i);
        return numa;
    }
    //归并排序
    public static int[] mergeSort(int[] num) {
        int n = num.length;
        //每一个数组装一半元素
        int[] numb = new int[n / 2];
        int[] numc = new int[n - (n / 2)];
        //递归过程中当某个数组长度小于等于1时结束
        if(num.length > 1) {
            //将前半部分复制到numb中，后半部分复制到numc中
            System.arraycopy(num, 0, numb, 0, n / 2);
            System.arraycopy(num, n / 2, numc, 0, n - (n / 2));
            //对两个子数组进行排序
            mergeSort(numb);
            mergeSort(numc);
            //将排好序的numb和numc合并
            merge(numb, numc, num);
        }
        return num;
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        int n = in.nextInt();
        int[] num = new int[n];
        
        for(int i = 0; i < num.length; i++)
            num[i] = in.nextInt();
        
        //调用算法
        num = mergeSort(num);
        for(int i = 0; i < num.length; i++)
            System.out.print(num[i] + " ");
        
        in.close();
    }
}