← 返回 twosigma 的题目列表Implement Merge Sort
类型：online_judge
Implement merge sort. Given an integer array arr of length n, output the array sorted in ascending order.
Requirements:
Use the merge sort paradigm (divide-and-conquer + merge).
You may use O(n) extra space.
Constraints:
1 <= n <= 2e5
-1e9 <= arr[i] <= 1e9
I/O format:
Input: n, then n integers
Output: the sorted n integers (space-separated)
Example:
Input:
5
5 2 3 1 4
Output:
1 2 3 4 5
Example
Input
5
5 2 3 1 4
Output
1 2 3 4 5