[알고리즘] 합병 정렬 (Java)

합병 정렬 정렬 알고리즘의 한 종류인 합병 정렬입니다. 합병정렬의 기본 개념은 n 개의 부분 리스트로 분할하는 것입니다. 흔히 쓰이는 하향식 2-way 합병 정렬에서의 과정입니다. 리스트 길이가 1이하면 이미 정렬된 것으로 봅니다. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분을 리스트로 나눕니다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용 정렬합니다. 두 부분 리스트를 다시 하나의 리스트로 합병합니다. 합병 정렬의 시간 복잡도는 O(nlogn)입니다. 합병 정렬 과정입니다. 먼저 최소 배열 단위까지 분할 후 합병 과정에서 분할된 두개의 배열의 각 인덱스를 비교하여 정렬을 합니다. 이 과정에서 임시 배열에 정렬된 배열을 저장하고 정렬 후에 기존 배열에 임시 배열을 복사합니다. 다음은 Java를 이용하여 구현해 보겠습니다. public static void main(String[] args) { int[] arr = {30, 15, 20, 25, 40, 45, 35,...

원문링크 : [알고리즘] 합병 정렬 (Java)