합병정렬
-
[간단 정리] 합병 정렬알고리즘/프로그래머스 2019. 11. 28. 17:21
* 오름차순 기준입니다 이름에서 알 수 있듯이 합병의 과정에서 데이터가 정렬되는 알고리즘이다. 합병하기 위해선 분할을 해야겠지? 합병 정렬은 분할 정복 알고리즘에 속한다. 연결 리스트로 구현하면 퀵 정렬을 포함한 어느 정렬 알고리즘보다 효율이 좋다고 하지만 배열로 공부했기 때문에 여기에선 배열을 사용한다. 최소 단위까지 분할을 하고 나서 합병하면서 대소를 비교해 정렬한다. 분할한다고 해서 매번 그 과정에 배열을 진짜로 나누진 않는다. 인덱스를 가지고 구간을 분할하며, 합병할 때 배열이 등장한다. 주어진 배열에 left, mid, right가 있을 때 분할하는 범위는 left ~ mid와 mid+1 ~ right이다. 나눠서 수행하며 재귀호출로 분할할 수 없을 때까지 분할한다. 즉 마지막까지 분할되면 왼쪽..