JavaHardSorting & Searching35 min
Sort an array using merge sort
Print the array in ascending order using merge sort, with values separated by single spaces. Follow the stated ordering and edge-case conventions exactly. Interviewers use this task to probe algorithm selection, invariants, and boundary handling.
Input
n followed by n integers.
Output
Print the array in ascending order using merge sort, with values separated by single spaces.
Constraints
0 <= n <= 100000; values in [-1000000000,1000000000].
Example
Input
5 5 1 4 2 3
Output
1 2 3 4 5
Example 2 input
6 1 2 3 4 5 6
Output
1 2 3 4 5 6
This example exercises a further boundary or ordering case.
Public test cases (2)
Input
5 5 1 4 2 3
Expected output
1 2 3 4 5
Input
4 2 2 1 1
Expected output
1 1 2 2
Hints (2)
- Identify the state needed to avoid recomputing work for each element.
- Iteratively merge sorted runs of doubling width using a reusable auxiliary array.
Target complexity: time O(n log n) · space O(n)