병합정렬이란?

어떤 문제를 우선 작은 문제로 쪼개고 난 후 다시 조합하여 원래의 문제를 푸는것,
분할과 정복과정으로 이루어져있음

병합정렬 이해하기

분할

[5, 10, 66, 77], [54, 32, 11, 15]
[5, 10], [66, 77], [54, 32], [11, 15]
[5], [10], [66], [77], [54], [32], [11], [15]

정복
: 그룹의 0번째끼리 비교하여 작은것이 앞쪽으로 오도록 함

[5, 10], [66, 77], [32, 54], [11, 15]

// 1) 5와 66을 비교함
원본: [], [10], [66, 77], [32, 54], [11, 15] 
결과값: [5]

// 2) 10과 66을 비교함
원본: [], [], [66, 77], [32, 54], [11, 15] 
결과값: [5, 10]

// 3) [66, 77]은 이미 정렬된 상태이므로 그대로 가지고옴
원본: [], [], [],  [], [32, 54], [11, 15] 
결과값: [5, 10, 66, 77]

// 4) 나머지에 반복
원본: [], [], [], [], [], [], [], []
결과값: [5, 10, 66, 77], [11, 15, 32, 54]

// 다시 0번째끼리 비교
[5, 10, 66, 77], [11, 15, 32, 54]

원본: [], [], [66, 77], [], [], [], []
결과값: [5, 10, 11, 15, 32, 54]

// 남은 66, 77은 이미 정렬된 상태이므로 통째로 넣어준다.
결과값: [5, 10, 11, 15, 32, 54, 66, 77]

재귀함수를 이용한 병합정렬

let 입력값 = [5, 10, 66, 77, 54, 32, 11, 15];

분할

function 병합정렬(입력배열) {
    let 입력배열의길이 = 입력배열.length;
    if(입력배열의길이 <= 1) {
        return 입력배열
    }
    let 중간값 = parseInt(입력배열의길이/2);
    let 그룹하나 = 병합정렬(입력배열.slice(0, 중간값));
    let 그룹둘 = 병합정렬(입력배열.slice(중간값, )); // 비워두면 알아서 마지막까지 자름
    return `그룹하나 : ${그룹하나} 그룹둘 : ${그룹둘}\n`
}

console.log(병합정렬(입력값));

// 결과
그룹하나 : 그룹하나 : 그룹하나 : 5 그룹둘 : 10
그룹둘 : 그룹하나 : 66 그룹둘 : 77

그룹둘 : 그룹하나 : 그룹하나 : 54 그룹둘 : 32
그룹둘 : 그룹하나 : 11 그룹둘 : 15

아래 그림처럼 분할되어있는 상태이다.

정복

function 병합정렬(입력배열) {
    let 입력배열의길이 = 입력배열.length;
    let 결과값 = [];  // 정렬된 값을 넣어줄것
    if(입력배열의길이 <= 1) {
        return 입력배열
    }
    let 중간값 = parseInt(입력배열의길이/2);
    let 그룹하나 = 병합정렬(입력배열.slice(0, 중간값));
    let 그룹둘 = 병합정렬(입력배열.slice(중간값, ));

   // 그룹하나와 그룹둘이 모두 요소가 존재할 때
    while(그룹하나.length != 0 && 그룹둘.length != 0) {
        if(그룹하나[0] < 그룹둘[0]) {
            결과값.push(그룹하나.shift());
        } else {
            결과값.push(그룹둘.shift());
        }
    }
  
	// 그룹하나에만 값이 있을때
    while(그룹하나.length != 0) {
            결과값.push(그룹하나.shift());
    }

    // 그룹둘에만 값이 있을때
    while(그룹둘.length != 0) {
            결과값.push(그룹둘.shift());
    }

    return 결과값;
}

console.log(병합정렬(입력값)); // [5, 10, 11, 15, 32, 54, 66, 77]

최종코드

function 병합정렬(입력배열) {
    let 입력배열의길이 = 입력배열.length;
    let 결과값 = [];  // 정렬된 값을 넣어줄것
    if(입력배열의길이 <= 1) {
        return 입력배열
    }
    let 중간값 = parseInt(입력배열의길이/2);
    let 그룹하나 = 병합정렬(입력배열.slice(0, 중간값));
    let 그룹둘 = 병합정렬(입력배열.slice(중간값, ));

   // 그룹하나와 그룹둘이 모두 요소가 존재할 때
    while(그룹하나.length != 0 && 그룹둘.length != 0) {
        if(그룹하나[0] < 그룹둘[0]) {
            결과값.push(그룹하나.shift());
        } else {
            결과값.push(그룹둘.shift());
        }
    }
  
	// 그룹하나에만 값이 있을때
    while(그룹하나.length != 0) {
            결과값.push(그룹하나.shift());
    }

    // 그룹둘에만 값이 있을때
    while(그룹둘.length != 0) {
            결과값.push(그룹둘.shift());
    }

    return 결과값;
}

console.log(병합정렬(입력값)); // [5, 10, 11, 15, 32, 54, 66, 77]