합병 정렬이 무엇일까

합병 정렬#

입력받은 배열을 1자리가 될 때까지 나눈 뒤 정렬하며 합치는 알고리즘이다

두 배열을 합쳐주는 함수 merge 배열을 둘로 나누고 값을 반환할 함수 mergeSort 정렬할 배열은 [5,4,3,2,1]로 했을 때를 간단하게 그려보았습니다

그림과 같이 좌우로 절반을 나누어 1자리가 될 때 까지 실행한뒤 1자리가 되면 좌우로 나눴던 배열을 비교하여 정렬 후 합치게 된다

이번엔 코드를 보자

먼저 두 배열을 합치는 merge 함수이다#

1
function merge(arr1,arr2){
2
	const result = []; // 정렬한 배열
3
    let i = 0;
4
    let j = 0;
5

6
    while(i< arr1.length && j < arr2.length){
7
    	if(arr2[j] > arr1[i]){
8
        	result.push(arr1[i]);
9
          	i++;
10
        }
11
      	else{
12
        	result.push(arr2[j]);
13
          	j++;
14
        }
15
    }
16

17
  	// 한 쪽이 빨리 끝난다면 나머지들 push
18
  	while(i < arr1.length){
19
    	result.push(arr[i]);
20
      	i++;
21
    }
22

23
  	while(j < arr2.length){
24
    	result.push(arr[j]);
25
      	j++;
26

27
}
28

mergeSort함수#

1
function mergeSort(arr) {
2
  if (arr.length <= 1) return arr;
3
  const mid = Math.floor(arr.length / 2);
4
  const left = mergeSort(arr.slice(0, mid));
5
  const right = mergeSort(arr.slice(mid));
6

7
  return merge(left, right);
8
}

정렬할 배열 arr를 좌우로 나누어 한 자리가 될 때 까지 재귀를 통해 반복한다 한 자리 수가 되면 left,right값이 정해지기 떄문에 merge(left,right) 실행하여 얻은 정렬된 배열을 반환한다 이를 반복하여 최종적으로 정렬이 된 배열을 반환한다

한동룡