머지소트
-
합병정렬 알고리즘 :: 마이구미알고리즘 2018. 4. 14. 16:28
이 글은 합병정렬(merge sort) 또는 머지소트 라고 불리는 정렬 알고리즘을 다룬다.누구나 한번쯤 들어봤고, 구현해본 정렬 중 하나이다.빠른 정렬에 분류되고 퀵정렬과 많이 언급되는 정렬이다.이유는 분할 정복 방식을 따르기 때문이다.퀵 정렬 - http://mygumi.tistory.com/308 1. 합병정렬이란 무엇인가?2. 합병정렬은 어떻게 구현하는가?3. 합병정렬의 유용한 예는 언제인가? 합병정렬은 분할 정복 방법을 통해 구현된다.분할 정복이란, 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식이다.(* 이전 글에서 다룬 퀵정렬도 분할 정복 방식을 가진다.) 시간복잡도는 최악, 최선, 평균 모두 O(nlogn) 을 가진다.또한 안정 정렬로 속한다. (안정 정렬의 의미를 모른다면 참고글) ..