Merge Sort(합병정렬)

합병 정렬 또는 병합 정렬은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945년에 개발했다. 위키백과

• 안정 정렬
• 분할 정복 알고리즘
  • 분할 정복 알고리즘(divide and conquer)은
    • 문제를 작은 2개의 문제로 분리해 각각 해결한 후, 결과를 모아 원래의 문제를 해결하는 전략
    • 보통 순환 호출을 통해 구현

1. 리스트의 길이가 0또는 1이면 이미 정렬된 것으로 봄
2. 리스트 길이가 2 이상이라면 리스트를 절반으로 나누어 비슷한 크기의 두 부분리스트로 나눔
3. 각 부분 리스트를 재귀적으로 합병정렬로 정렬
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병

합병정렬 알고리즘

• 분할
• 정복
• 결합

이 세가지 단계로 이뤄짐

ex1)

[21, 10, 12, 20, 25, 13, 15, 22] 배열이 있다고 할 때,

1. 2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트(sorted)로 옮긴다.
2. 둘 중에서 하나가 끝날 때까지 이 과정을 되풀이한다.
3. 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 값들을 전부 새로운 리스트(sorted)로 복사한다.
4. 새로운 리스트(sorted)를 원래의 리스트(list)로 옮긴다.