题目描述

归并排序

样例

输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5

算法1

(递归合并) $O(nlogn)$

1. 确定分界点 mid = (l+r)/2
2. 递归排序 left right
3. 归并：合二为一 (重点) 双指针算法

时间复杂度

时间复杂度为$O(nlogn)$ 每次从中间位置递归 深度为$O(logn)$，每次合并的复杂度为$O(n)$ 所以时间复杂度为$O(nlogn)$

Java 代码

import java.util.*;

public class Main{
    static int[] tmp;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        tmp = new int[n];
        for(int i = 0;i<n;i++)
            arr[i] = sc.nextInt();
        mergeSort(arr,0,n-1);
        for(int i = 0;i<n;i++)
            System.out.print(arr[i]+" ");
    }
    public static int[] mergeSort(int[] arr,int l,int r){
        if(l>=r) return arr;
        int mid = l+r>>1;
        mergeSort(arr,l,mid);mergeSort(arr,mid+1,r);
        int i = l,j = mid+1,k = 0;

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