정렬(Sort) 알고리즘 - 병합정렬 MergeSort (C#)

정렬 알고리즘 중 이번엔 병합정렬(MergeSort)를 알아보겠습니다.

 

병합 정렬은 두개씩 묶어서 정렬을 하고 병합을 시키는 정렬입니다.

 

이미지와 같이 두개씩 묶어서 배열을 만들고 정렬을 시켜줍니다.

 

묶인 배열을 시작과 중간을 나눠서 서로 비교하여 정렬을 합니다.

 

전부 정렬이 완료되면 아래와 같은 형태로 정렬이 되었습니다.

병합된 정렬을 시작과 중간으로(반으로) 나눠서 다시 정렬합니다.

2와 0을 비교하여 0이 작기 때문에 0이 들어가고

2와 7이 비교가 되며 2가 작으므로 2가 다음으로 들어갑니다.

8과 7을 비교하여 7이 작기 때문에 7이 들어가고 마지막으로 8만 남았기 때문에 8을 넣어줍니다.

 

이런식으로 분할 해서 정렬 후 병합을 반복하면 최종적으로 정렬이 된 배열이 됩니다.

재귀호출을 하면서 정렬할 배열들을 나눠줍니다.

Merge함수에서 임시 배열에 현재 배열데이터를 넣어주고 정렬을 시작합니다.

로그를 심어 비교하여 정렬된 데이터와 비교 데이터가 없어서 남는 데이터가 들어가는 과정을 확인 할 수 있게 하였습니다.

 

감사합니다.