题目描述

给定你一个长度为n的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出

样例

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

Java 代码

import java.util.Scanner;

public class Main {
    public static void mergeSort(int q[], int l, int r) {
        if (l >= r) return;

        int mid = l + r >> 1;
        mergeSort(q, l, mid);
        mergeSort(q, mid + 1, r);

        int[] tem = new int[r - l + 1];
        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (q[i] <= q[j]) tem[k++] = q[i++];
            else tem[k++] = q[j++];
        }

        while (i <= mid) tem[k++] = q[i++];
        while (j <= r) tem[k++] = q[j++];

        for (i = l, j = 0; i <= r; i++, j++) q[i] = tem[j];
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = Integer.parseInt(in.nextLine());
        int[] arr = new int[num];
        String[] strArr = in.nextLine().split(" ");
        for (int i = 0; i < num; i++){
            arr[i] = Integer.parseInt(strArr[i]);
        }

        mergeSort(arr, 0, num - 1);

        for (int i = 0; i < num; i++) {
            System.out.print(arr[i] + " ");
        }
        in.close();
    }
}