Merge Sort (합병 정렬) python으로 구현하기

- Merge Sort 설명 

✔  divide & conquer방법을 이용함
✔ n개의숫자들을 반으로 나눠 2개의 부분으로 분할하고 → 각각의 부분을 재귀적으로 정렬한 후 →  2개의 정렬된 부분을 merge하여 정렬 

 

 

- Mergesort 

(1) 1개의 정렬되지 않은 배열을 2개의 배열로 분할하는것을 반복 → 배열의 원소 갯수가 1개가 될때까지 반복  

(2) 양쪽의 배열의 크기가 둘 다 1개가 되면 merge시켜준다   

 

✔ 입력 크기가 n=6 , list A= [ 9,  20,  5,  15,  3,  11  ]인 경우  

Mergesort의 전체적인 과정

초록색 화살표는 divide하는 과정, 노란색 화살표는 merge하는 과정을 의미한다. 

 

 

- Merge

✔ 두개의 정렬된 배열을 하나의 정렬된 배열로 합치는 function
✔ A=[1,,,,h] 와 B=[1,,,,m]을 merge하여 S=[1,,,,,h+m] 으로 합친다

 

merge하는 과정

< 순서 > 
(1) i, j=0부터 시작한다
(2) A[i], A[j]값을 비교해서 작은 값을 list S에 넣어준다. 
(3) 작은 값의 index를 1개 증가해줄것 (i+=1 or j+=1) 

 

 

- python code (Merge)

 

 

- python code (MergeSort)