Implement Merge

Exercise Open the starter code, the Demo.java file and complete the implementation of merge. Your implementation must have time complexity of $O(n)$.

Hint: It is possible to implement merge with $O(1)$ auxiliary space (so the whole merge sort process would be in-place). However, it adds unnecessary complexity to the implementation, which gets the essential idea behind the linear-time merge process. So, feel free to implement merge with $O(n)$ auxiliary space.