popo story popo story

합병 정렬은 분할 정복 알고리즘에 속한다 * 분할 정복 알고리즘 : 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘 합병 정렬은 n개의 숫자를 n/2개씩 2개의 부분 문제로 분할하여 1개가 남을때까지 분할하고 분할한 숫자들을 다시 합병하며 정렬한다 즉, 작은 문제로 쪼개고 다시 조합한다는 것이다 - n개의 숫자들을 n/2개씩 2개의 부분 문제로 분할 - 각각의 부분 문제를 순환으로 합병 정렬 - 2개의 정렬된 부분을 합병하여 정렬(정복) 예를 들어 이런 배열이 있다고 하자 그 후 이 배열을 계속 2로 나누어 하나가 남을때까지 쪼갠다 이렇게 하나 남을 때까지 배열을 모두 쪼개고 다시 합칠 때 정렬을 해준다 그림으로 보면 합병 정렬의 원리가 더 이해가 잘 될것이다 합병 정렬의 시간 복잡..