주요 내용으로 건너뛰기

알고리즘 연습: merge sort

정렬 알고리즘 - 1

Merge sort는 divide & conquer 전략을 통해 전체 array를 반으로 계속 쪼개어

모든 sub array를 sorted 상태로 만든 다음 merge 작업을 통해 정렬하는 방식이다.

시간 복잡도는 O(n)의 복잡도를 가진 삽입정렬보다 낮은 O(NlgN)으로 

정렬 알고리즘 중에서는 가장 빠른 편에 속한다.

다음은 이 알고리즘을 javascript로 구현한 예시이다.

다음 예시는 paullewis의 gist(https://gist.github.com/paullewis/1982121)를 바탕으로 작성했으며,

원리는 

1. 모든 sub array가 sorted 상태가 될 때가지, 즉 원소가 하나만 남을 때까지 분할한 다음

2. merge 함수를 이용해 각각의 sub array 의 원소 간 크기 비교를 시행하여

   새로운 결과 array에 크기가 상대적으로 작은 원소를 집어넣는 방식이다.



이준형 님의 창작활동을 응원하고 싶으세요?

댓글

SNS 계정으로 간편하게 로그인하고 댓글을 남겨주세요.