Merge Sort - Classic Problems | Repovive

CLS23. Merge Sort

1s256 MB

Given an array of $n$ integers, sort them in non-decreasing order.

Implement the Merge Sort algorithm, which divides the array into halves, recursively sorts each half, and merges them back together.

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

$a_1 \quad a_2 \quad \cdots \quad a_n \text{ (sorted)}$

Input

8
3 1 4 1 5 9 2 6

Explanation

For this input, the required output is 1 1 2 3 4 5 6 9.

Output

1 1 2 3 4 5 6 9

Input

5
5 4 3 2 1

Explanation

For this input, the required output is 1 2 3 4 5.

Output

1 2 3 4 5

Input

4
7 7 7 7

Explanation

For this input, the required output is 7 7 7 7.

Output

7 7 7 7

Given an array of $n$ integers, sort them in non-decreasing order.

Implement the Merge Sort algorithm, which divides the array into halves, recursively sorts each half, and merges them back together.

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

$a_1 \quad a_2 \quad \cdots \quad a_n \text{ (sorted)}$