AcWing 787. Merge sort (template)

Activities - AcWing

 

【 Merge sort 】 Like fast platoon, it is also the idea of partition

（1） Determine the cut-off point

（2） The two sides of the dividing point are sorted respectively

（3） Merge two ordered arrays

（4） Copy back to the original array

Proper O(nlogn) Time complexity of , Required for consolidation O(n) Time for , common logn layer

package AcWing.course;
import java.io.StreamTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class _787_ Merge sort _1 {

    // 8：38 8:50
    static int n;
    static int[] arr, tmp;
    static StreamTokenizer st;

    static int nextInt() throws Exception {
        st.nextToken();
        return (int)st.nval;
    }

    static void mergeSort(int l, int r){
        if(l >= r) return;
        int mid = (l + r) >>> 1, i = l, j = mid + 1, k = 0;
        mergeSort(l, mid); mergeSort(mid + 1, r);
        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; j < k; j++, i++) arr[i] = tmp[j];
    }

    public static void main(String[] args) throws Exception {
        st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter pw = new PrintWriter(System.out);
        n = nextInt();
        arr = new int[n];
        tmp = new int[n];
        for(var i = 0; i < n; i++) arr[i] = nextInt();
        mergeSort(0, n - 1);
        for(var x: arr){
            pw.print(x);
            pw.print(" ");
        }
        pw.flush();
    }

}