병합정렬

일단 반으로 나누고 나중에 합쳐서 정렬하면 어떨까?

<작동방식>

1. 리스트를 반으로 나눕니다.
2. 왼쪽 부분과 오른쪽 부분을 각각 병합 정렬을 사용하여 정렬합니다.
3. 정렬된 왼쪽 부분과 오른쪽 부분을 병합합니다.

<예시>

예시에는 시작에서 리스트에서 전부 나누었습니다.

 

1번에서는 7,6을 비교하여 정렬을 했습니다.

 

2번에서는 6,7 과 5,8를 비교하여 정렬했습니다.

 

3번에서는 5,6,7,8과 1,3,5,9비교 하여 정렬했습니다.