Merge Sorted Array

You are given two sorted arrays. The first array contains m valid elements followed by extra space (filled with zeros) to accommodate n elements from the second array. Your task is to merge the second array into the first one in a sorted order using an in-place algorithm.

The expected time complexity is \(O(m+n)\).

inputFormat

The first line contains two integers \(m\) and \(n\), where \(m\) is the number of valid elements in the first array and \(n\) is the number of elements in the second array.

The second line contains \(m\) space-separated integers representing the sorted first array.

The third line contains \(n\) space-separated integers representing the sorted second array. If \(m\) or \(n\) equals 0, the corresponding line will be empty.

outputFormat

Output the merged sorted array in a single line with each element separated by a space.

3 3
1 2 3
2 5 6

1 2 2 3 5 6