병합 정렬 (Merge Sort)

병합 정렬 (Merge Sort)는 고오급 정렬 알고리즘에 속한다 그 중 분할 정복 알고리즘에 속한다 (그 이유는 정렬을 하는 방법을 보면 쉽게 와닿는다!) 정렬 알고리즘은 다음과 같다 1. 배열의 반을 뚝 하고 자른다 2. 배열의 원소 수가 1개 이하가 될때까지 1을 반복한다 3. 배열의 원소 수가 1개 이하가 되면 정렬된 것으로 간주한다 (하나밖에 없으니까!) 4. 분할되었던 2개의 배열을 합치며 양 배열의 순서에 맞는 값을 집어넣으며 분할되었던 모든 배열을 합친다 5. 정렬 끝! 따라서 병합 정렬은 재귀함수를 통해 구현하게 된다 이를 간단하게 그림으로 표현하자면 이렇게 된다 실제로는 동시에 진행되지 않고, 잘게 쪼개서 부분 하나하나씩 정렬해 갈 것이다 이를 코드로 구현하면 다음과 같다 // 이 함수..

2023.02.10