가치투자자

병합 정렬 (merge sort) 1. 병합 정렬이란? 병합 정렬(merge sort)은 어떤 문제를 2개의 작은 문제로 분리해 각각 해결한 다음, 이걸 모아서 원래 문제를 해결하는 분할 정복 알고리즘 중 하나다. 병합 정렬 알고리즘은 다음 개념들을 바탕으로 진행된다. 분할(Divide) : 입력된 배열을 같은 크기의 부분 배열 2개로 분할한다. 정복(Conquer) : 부분 배열의 크기가 충분히 작지 않으면(리스트의 길이가 0 또는 1이 아니면) 다시 분할을 한다. 결합 (Combine) : 정렬된 부분 배열들을 하나의 배열에 병합한다. 병합 정렬은 다음 단계들로 진행된다. 부분 배열의 요소들을 결합할 빈 배열이 필요하다. 부분 배열의 크기(length)가 1이 될 때까지 쪼개준다. 부분 배열의 0번째..