Problem: AcWing 787. 归并排序

思路

归并排序是一种分治算法。首先将数组分为两半，然后对每一半进行排序，最后将两个已排序的部分合并在一起。这个过程会递归地应用到每一半。

解题方法

如果数组只有一个元素，那么它已经排序了，直接返回。
否则，找到数组的中点，将数组分为两半。
对每一半递归地进行归并排序。
将两个已排序的部分合并在一起。

复杂度

时间复杂度:

归并排序的时间复杂度为$O(nlogn)$，其中n是数组的长度。这是因为算法每次将数组分为两半，然后对每一半进行排序，所以时间复杂度为$O(logn)$。然后，合并两个已排序的部分的时间复杂度为$O(n)$。因此，总的时间复杂度为$O(nlogn)$。

空间复杂度:

归并排序需要一个与原数组同样大小的辅助数组，所以空间复杂度为$O(n)$。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	static StreamTokenizer sr = new StreamTokenizer(in);
	static int n;
	static int MAXN = (int) (1e5 + 10);
	static int[] arr = new int[MAXN];
	static int[] help = new int[MAXN];

	public static void main(String[] args) throws IOException {
		n = nextInt();
		for (int i = 0; i < n; i++) {
			arr[i] = nextInt();
		}
		mergeSort(0, n - 1);
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < n; i++) {
			sb.append(arr[i]);
			sb.append(" ");
		}
		out.println(sb);
		out.flush();

	}

	private static void mergeSort(int l, int r) {
		if (l == r) {
			return;
		}
		int m = (l + r) / 2;
		mergeSort(l, m);
		mergeSort(m + 1, r);
		merge(l, m, r);
	}

	private static void merge(int l, int m, int r) {
		int i = l;
		int a = l;
		int b = m + 1;
		while (a <= m && b <= r) {
			help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
		}

		while (a <= m) {
			help[i++] = arr[a++];
		}
		while(b <= r) {
			help[i++] = arr[b++];
		}
		for(int j = l; j <= r; j++) {
			arr[j] = help[j];
		}

	}

	static int nextInt() throws IOException {
		sr.nextToken();
		return (int) sr.nval;
	}

}