정렬알고리즘_병합정렬

병합정렬(merge sort)

병합의 개념 : 두개 이상의 정렬된 자료집합을 하나의 정렬된 자료집합으로 합치는 것

병합의 방법 : 대상 자료집합이 정렬된 상태이므로 순차적으로 작은 자료를 뽑아서 놓으면됨

장점 :안정적인 정렬 방법

데이터의 분포에 영향을 덜 받는다.

즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. (O(nlog₂n)로 동일)

단점 :

만약 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다.

제자리 정렬(in-place sorting)이 아니다.

(나열된 것 중에 가장 작은 또는 가장 큰 것을 선택하여 앞 또는 끝으로 보내는 작업을 반복하여최종적으로 크기 순서대로 정렬이 되는 방식.(오름차순 , 내림차순))

두 집합이 병합되는 부분

i: 정렬된 왼쪽 리스트에 대한 인덱스

j: 정렬된 오른쪽 리스트에 대한 인덱스

k: 정렬될 리스트에 대한 인덱스

실제로 숫자들이 정렬되는 과정