배열 합쳐서 정렬하기⭐⭐⭐

정렬된 배열A,B가 주어지면 배열을 합친 후 다시 정렬하는 프로그램을 작성하시오.

일단 문제를 보고 정처기에서 나왔던 mergeSort 가 생각났지만 알고리즘 자체가 생각 나지 않았습니다...
어떤식으로 풀가 생각중 이전 ArrayList에서 정렬 하는 메소드를 썼던적이 있어서 그부분을 이용해서 풀어보겠습니다.

ps. 정답이 아닐수도 있어요 출제자의 의도는 이게 아닐거 거든요...

입력
첫 번쨰 줄에 배열A, B의 크기 순서대로 입력
다음 줄에 배열 A의 내용, 그 다음 줄에 배열 B의 내용 입력

출력
두 배열을 합친 결과 출력한다.

import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		
		String[] Size = input.split(" ");
		
		int leng = Integer.valueOf(Size[0]) +  Integer.valueOf(Size[1]);
		

		ArrayList<Integer> arr = new ArrayList<Integer>(leng);
		String input1= br.readLine();
		String[] Size1= input1.split(" ");
		for(int i = 0; i < Size1.length; i++){
			arr.add(Integer.valueOf(Size1[i]));
		}
		String input2= br.readLine();
		String[] Size2= input2.split(" ");
		for(int i = 0; i < Size2.length; i++){
			arr.add(Integer.valueOf(Size2[i]));
		}
		
		
		arr.sort(Comparator.naturalOrder());
		for(int i = 0; i < arr.size(); i++){
			System.out.print(arr.get(i)+" ");
		}
	}
}

일단 먼저 두 배열의 사이즈를 구하여서 leng에 저장한 다음 그 크기만큼 ArrayList를 만들어 줍니다.

그리고 ArrayList에 배열 A, B를 차곡차곡 넣어준 후
Comparator.naturalOrder() → 오름차순
Comparator.reverseOrder() → 내림차순
을 사용하여 정렬 후

순서대로 출력해줍니다.