merge sort

1. 배열을 반씩 쪼개야
2. 쪼개진 배열의 앞의 것부터 길이가 1이 될때까지 쪼갬(길이가 1인 배열이 되어야만 비로소 합치는 행동을 시작)
3. 길이가 1인 배열 2개를 비교해서 정렬,길이가 1인 모든 배열들에 대해 진행
4. 정렬된 원소 2개짜리 배열을 합침(이렇게 합쳐진 배열들은 크기순대로 정렬된 상태),이것을 계속 반복

시간 복잡도

병합 정렬은 분할과 병합 단계로 나뉘는데 분할 단계는 시간 복잡도에 포함되지 않는다. 병합 정렬의 시간 복잡도는 worst case, best case 모두 다 O(n log n)이다.

• worst case : O(n log n)
• best case : O(n log n)

장점

worst case , best case 어떤 경우에도 좋은 성능이 보장된다.
또 중복 값의 위치가 변하지 않는다(stable)

단점

메모리 공간이 필요하다.
분할할 때 데이터 요소의 양만큼 새로운 메모리 공간이 필요하다(not in place)

const divide = (array) => {
    if (array.length < 2) {
        return array
    }
    const mid = Math.floor(array.length / 2)
    const smallOne = array.slice(0, mid)
    const smallTwo = array.slice(mid)
    return merge1(divide(smallOne), divide(smallTwo))
}

const merge1 = (smallOne, smallTwo) => {
    const sorted = [] //결과 담을 배열이 필요(quick sort에 비해 메모리를 추가적으로 써야 한다)
    while (smallOne.length && smallTwo.length) {
        smallOne[0] <= smallTwo[0] ? sorted.push(smallOne.shift()) : sorted.push(smallTwo.shift())
    }
    const output = [...sorted, ...smallOne, ...smallTwo]
    return output
}

const numbers = [8, 5, 6, 9, 3, 1, 4, 2, 7, 10]
console.log(divide(numbers))

실행 순서(헷갈려서 하나씩 써봄)

const numbers = [8, 5, 6, 9, 3, 1, 4, 2, 7, 10];
/* 
쪼개고 정렬하고 쪼개고 정렬하고를 반복, 즉 길이가 1인 배열 2개 생기면 그 둘을 
비교해서 정렬

1st.
divide( [8, 5, 6, 9, 3, 1, 4, 2, 7, 10]  )
 left           right
[8,5,6,9,3]     [1,4,2,7,10]
divide( [8, 5, 6, 9, 3, 1, 4, 2, 7, 10]  ) =
merge1(  divide([8,5,6,9,3])  , divide([1,4,2,7,10])  )

divide([8,5,6,9,3])완료 후 divide([1,4,2,7,10])실행, 
이 둘 다 실행 후 merge1의 인자로 들어가서 최종정렬 된다

2nd.
divide( [8,5,6,9,3]) 
left        right
[8,5]     [6,9,3]

divide( [8,5,6,9,3]) = merge1(   divide([8,5]), divide([6,9,3])   )

3rd.
divide( [8,5] ) 
= merge1( divide([8]), divide([5]))=merge1([8],[5])
= [5,8]

left    right
 [8]       [5]

 4rd.
 merge1( divide([8]), divide([5]) );
 merge1( [8] , [5] ) => 5 < 8 
 sorted = [5] left = [8] right = []

 merge1( divide([8]), divide([5]) ) = [5,8](output)  -> 정렬 완료

5rd.
divide ([6,9,3]) = merge1( divide([6], divide([9,3] );
left     right
[ 6 ]      [ 9, 3]

6th.
divide([6])=[6]

7rd.
divide( [9,3] ) =
 merge1(divide[9] , divide[3]) =merge1( [9], [3]);
 =[3,9](output)

left right 
 [9]  [3]
sorted  left    right
 [3]      [9]     []

8th.
merge1([6],[3,9]) = [3,6,9] 

여기까지 처음 divide( [8,5,6,9,3])완료
...나머지는 같은 것 반복

*/

퀵 정렬, 병합 정렬 차이점

퀵 정렬

• 새로운 배열 생성 위해 메모리 공간이 더 필요하지X(재귀 콜 스택을 위한 메모리만 사용됨)
• unstable (원소들 중에 같은 값이 있는 경우에 정렬 이후 순서가 초기 순서와 달라 질 수 있다)

병합 정렬

• 매 번 새로운 배열을 만들어 내므로 메모리 공간이 더 필요)하고
• stable(같은 값의 원소들도 정렬 이후 순서를 그대로 유지)