<aside> 📖 Contents

</aside>

⚫️ 병합정렬 (Merge sort)

• 병합정렬은 전형적인 분할정복 (divide and conquer)알고리즘 중 하나
• 주어진 리스트를 병합정렬할 때, 일단 최소단위까지 나누어 놓은 뒤 (분할) 그 리스트들을 합치면서 (merge)정렬한다.

▪️ 병합정렬 (머지소트)의 동작방식

• 초기 상태의 리스트 하나를 두 개의 리스트가 되도록 분할해 나가면서 최종적으로 길이가 1이 될 때까지 분할한다.

  • 위와 같은 에시일 경우, 최종적으로 {6} {5} {3} {1} {8} {7} {2} {4} 로 분할된다.

• 길이 1로 분할된 애들을 다시 길이 2가 되도록 합쳐준다.

  • 먼저 {6} {5} 를 가져와서 하나의 리스트로 정렬된 상태로 저장 → {5, 6}
  • {3} {1} 도 마찬가지로 하나의 리스트로 정렬된 상태로 저장 → {1, 3}
  • {8} {7} → {7, 8}
  • {2} {4} → {2, 4}

• 길이 2인 부분 리스트들을 길이가 4인 부분리스트가 되도록 만들어준다. 왼쪽과 오른쪽 리스트를 비교하는데, 결과값이 더 작은 애들을 차례대로 결과리스트에 넣어주는 과정이다.

  • {5, 6} {1, 3}

    • 5와 1 비교 → 1이 작으니 결과리스트에 append → {1}
    • 5와 3비교 → 3이 작으니 결과리스트에 append → {1, 3}
    • 이미 오른쪽 리스트는 다 소진, 왼쪽 리스트에 남은 애들을 차례대로 결과리스트에 append → {1, 3, 5, 6}

  • {7, 8} {2, 4}

    • 7과 2 비교 → 2가 더 작으니 결과리스트에 append → {2}
    • 7과 4 비교 → 4가 더 작으니 결과리스트에 append → {2, 4}
    • 남은 7과 8까지 결과리스트에 append → {2, 4, 7, 8}

  • 코드로 구현할 때는, 결과리스트에 들어가지 못한 인덱스는 그대로 두고, 결과리스트에 들어간 인덱스를 한칸 증가시킨다.

    

    

• 이제 길이가 4인 부분 리스트들을 길이가 8인 부분리스트가 되도록 정렬

  • {1, 3, 5, 6} {2, 4, 7, 8}
    • 1과 2를 비교 → 1이 더 작으니 결과리스트에 append → {1}
    • 3과 2를 비교 → 2가 더 작으니 결과리스트에 append → {1, 2}
    • 3과 4를 비교 → 3이 더 작으니 결과리스트에 append → {1, 2, 3}
    • 🔁 반복
  • 처음 리스트 길이가 될 때까지 반복한다.

▪️ 시간복잡도 → O(nlogn)

• N개를 1개씩 남을 때까지 반으로 자르는 과정 → logN의 비용
• 그리고 합쳐지는 과정에서 N번의 비용이 듬
• 그래서 총 O(nlogn)
• 공간복잡도 측면에서는 비효율적일 수 있다.
  • 위에서 봤다시피, 부분리스트를 합칠 때 임시로 결과를 저장하는 배열이 또 필요하기 때문에 메모리 자원 측면에서는 비효율적일 수 있다.
• 꿀팁 🍯
  • 분할정복알고리즘이 비교적 버블, 선택, 삽입 정렬보다 성능이 좋다.
  • 시간초과가 나는 경우, 분할정복 알고리즘을 사용해보자.