Merge Sort

Practice this coding question on Coding Gurukul.

Problem statement

Given an array of n integers, sort it in nondecreasing order using Merge Sort. Split the array into halves, sort each half, and merge the sorted halves. Print the sorted array. Keep every occurrence of a repeated value. Negative values are allowed. Do not use a library sorting function. Target O(n log n) time. Worked example [5, -2, 5, 0, 1] becomes [-2, 0, 1, 5, 5]. Both copies of 5 remain.

Input format

First line: n. Second line: n integers.

Output format

Print the n sorted integers separated by spaces.

Constraints

1 <= n <= 100000; -10^9 <= a[i] <= 10^9.

Sample input

5
5 -2 5 0 1

Sample output

-2 0 1 5 5

Sign in to run or submit a solution in C++, Java or Python.