[Algorithm] 병합 정렬, Merge sorting - 안정적이고 빠르다
데이터를 정렬하는데는 다양한 방법이 있는데 그 중 시간 복잡도가 O(n lon n) 인 알고리즘이 빠른 편이라고 알려져 있다. 동일한 시간 복잡도를 가진 알고리즘으로는 quick sorting, merge sorting, heap sorting 등이 있다. 그 중 heap sorting을 가장 많이 사용했던 것 같긴 한데 오늘은 안정적이면서 이해하기 쉽고 외우기도 쉬운 merge sorting을 복기해보았다. 병합 정렬은 전체 데이터를 반씩 반씩 균일하게 나누어서 가장 작은 단위까지 쪼갠 후에 다시 합쳐서 비교하는 방식으로 정렬한다. 예를 들면, {7, 1, 4, 3} 라는 데이터를 내림차순으로 정렬해보자. - {(7, 1), (4, 3)} // 2개씩 나눔 - {(1, 7), (3, 4)} // 각 나..
더보기
