병합 정렬(merge sort) 알고리즘 파헤치기

1. 병합정렬(merge sort) 여러개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식 분할 정복 알고리즘을 활용함 주어진 자료를 최소 단위의 문제까지 나눈 다음에 차례대로 정렬해가면서 최종 결과를 얻어내는 방식 시간복잡도는 O(nlogn) 2. 개요 - 간단한 과정 - [69,10,30,2,16,8,31,22]를 병합정렬한다면?? 2-1) 분할과정 절반씩 자료를 왼쪽, 오른쪽으로 나눠가고 더 이상 쪼갤 수 없을때까지 반복해서 나눈다 2-2) 병합과정 가장 밑단의 왼쪽 부분집합과 오른쪽 부분집합의 원소 크기를 서로 비교하여 정렬하여 병합시키고, 최종 1개로 병합될때까지 반복함 3. 구현 길이가 1이면 정렬하지말고, 바로 return 길이가 1보다 크다면, 왼쪽과 오른쪽을 나눠준다..