题目描述

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

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

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

输入格式

输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在1~109范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000

输入样例

5
3 1 2 4 5

输出样例

1 2 3 4 5

归并排序

归并排序是建立在归并操作上的一种有效的排序算法，是采用分治法的典型应用，将已有序列的子序列合并，得到完全有序的序列
速度仅次于快速排序，是稳定的算法

在合并阶段是用两个指针来做比较，例如，我们需要将[2,5,7,8]和[1,3,4,6]合并为[1，2，3，4，5，6，7，8]

具体代码(java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));
        String str=bufferedReader.readLine();
        int len=Integer.parseInt(str);
        String[] strRes=bufferedReader.readLine().split(" ");
        bufferedReader.close();
        if(strRes.length!=len){
            System.out.print("Please enter the correct length");
            return;
        }
        int arr[]=new int[len];
        for (int i=0;i<len;i++){
            arr[i]=Integer.parseInt(strRes[i]);
        }

        mergeSort(arr,0,len-1);

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

    }

    private static void mergeSort(int[] arr, int l, int r) {
        if(l>=r){
            return;
        }
        int mid=l+r >> 1;
        mergeSort(arr,l,mid);
        mergeSort(arr,mid+1,r);

        int[] temp=new int[r-l+1];
        int i=l;
        int j=mid+1;
        int k=0;

        while (i<=mid && j<=r){
            if(arr[i] <= arr[j]){
                temp[k++]=arr[i++];
            }else {
                temp[k++]=arr[j++];
            }
        }
        while (i<=mid){
            temp[k++]=arr[i++];
        }
        while (j<=r){
            temp[k++]=arr[j++];
        }
        for(i=l,j=0;i<=r;i++,j++){
            arr[i]=temp[j];
        }
    }
}

具体代码(kotlin)

private fun mergeSort(arr: IntArray, l: Int, r: Int) {

    if (l >= r) {
        return
    }
    val mid = l + r shr 1
    mergeSort(arr, l, mid)
    mergeSort(arr, mid + 1, r)

    val temp = IntArray(r - l + 1)
    var i = l
    var j = mid + 1
    var k = 0

    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++]
        } else {
            temp[k++] = arr[j++]
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++]
    }
    while (j <= r) {
        temp[k++] = arr[j++]
    }
    i = l
    j = 0
    while (i <= r) {
        arr[i] = temp[j]
        i++
        j++
    }
}