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

오늘은 분할 정복을 사용하여 정렬하는 Merge Sort에 대해 알아보겠습니다 Merge Sort는 말 그대로 합치는 정렬입니다 각 부분을 합치는 과정 중에서 해당 값을 비교하여 작은 수와 큰 수를 정렬하는 방법입니다 분할 정복 (Divide and Conquer) 주어진 문제의 입력을 분할하여 작은 부분 문제로 만들고 해당 문제를 해결하여 마지막으로는 전체 문제를 해결하는 알고리즘 → 부분 문제로 나눌 수 없을 때까지 나누어 해결하여 큰 문제를 해결하는 방식 MergeSort의 경우 각 부분을 입력의 1/2로 나누어 총 분할 횟수는 log2n 입니다 위 그림처럼 자잘한 문제로 나누어 해당 문제를 풀어해결하는 알고리즘 합병정렬 (MergeSort) 병합 정렬이라고도 부르며 해당 정렬 알고리즘은 부분 문제..