Merge Sort (합병 정렬)

• merge할 때 추가적인 배열이 필요하므로, 제자리 정렬(in-place)이 아니다.

• 시간 복잡도는 O(NlogN)이다. 절반씩 split하므로 logN에 요소의 개수만큼 비교하고 합병하므로 N을 곱한다.

• 안정적이다(stable). 왼쪽 절반과 오른쪽 절반의 인덱스 i와 j 위치에 있는 요소를 비교하여, 같으면 위치를 바꾸지 않고 순서를 그대로 유지한다.