mergesort

합병정렬이란 퀵정렬을 보완해서 나온 정렬 방법이라고 생각된다.

 

퀵 정렬은 기준값을 세운 후 왼쪽 오른쪽에 각각에 나누면서 정렬을 한다. 따라서 나누면서 이진트리 형태를 띄게 된다.

 

이에 최악의 경우에는 시간복잡도가 N^2이다. 이를 개선하여 처음부터 나누어진 수들을 합치면서 정렬을 한다. 나뉜상태에서 하기 때문에 NlogN으로 시간 복잡도가 일정하다. 

 

코드로 표현하자면

위의 설명과 같이 시간 복잡도는 NlogN이다.