[C++ - TIL] 합병 정렬(Merge Sort)의 논리 구조와 조건식 설계 능력

🎮 주제 : 합병 정렬(Merge Sort)의 논리 구조와 조건식 설계 능력

태그 : #C++ #알고리즘 #합병정렬 #분할정복 #재귀함수 #동적할당 #조건식연습

---

📌 학습 요약

• 합병 정렬(Merge Sort)의 메커니즘 : 하나의 문제를 작은 두 개의 문제로 분리하고, 각각을 해결한 뒤 결과를 합치는 **분할 정복(Divide and Conquer)**의 전형적인 사례를 학습
• 병합(Combine)의 삼단계 구조 : 정렬된 두 부분 배열을 합칠 때, (1) 양쪽 비교 (2) 왼쪽 잔여분 복사 (3) 오른쪽 잔여분 복사라는 명확한 세 단계 흐름을 파악
• 인덱스 기반 조건식 설계 : "왼쪽 배열이 남아있음"을 left <= middle로, "전체 범위"를 end - start + 1로 변환하는 등 자연어 논리를 코드 조건식으로 치환하는 훈련 수행
• 메모리 및 위치 관리 : 동적 배열 할당(new)과 해제(delete[])의 짝을 맞추고, 병합된 데이터를 원본 배열의 정확한 시작점(start + i)에 덮어쓰는 디테일한 인덱스 제어 습득

---

🛠 주요 코드 및 구현 상세

1. 합병 정렬(Merge Sort) 재귀 구조

void merge_sort(int list[], int start, int end) {
    // 원소가 2개 이상일 때만 분할 진행
    if (start < end) {
        int middle = (start + end) / 2;
        
        // 1. 분할(Divide) & 정복(Conquer)
        merge_sort(list, start, middle);      // 왼쪽 반 정렬
        merge_sort(list, middle + 1, end);  // 오른쪽 반 정렬
        
        // 2. 결합(Combine)
        combine(list, start, middle, end);
    }
}

2. 데이터 병합(Combine) 핵심 로직

void combine(int list[], int start, int middle, int end) {
    int left = start;
    int right = middle + 1;
    int count = 0;
    
    // 병합된 결과를 임시 저장할 동적 배열 생성
    int* combineList = new int[end - start + 1];

    // [Step 1] 양쪽 배열에 비교할 원소가 모두 남아있을 때
    while (left <= middle && right <= end) {
        if (list[left] <= list[right])
            combineList[count++] = list[left++];
        else
            combineList[count++] = list[right++];
    }

    // [Step 2] 왼쪽 배열만 남았을 때 (오른쪽은 소진됨)
    while (left <= middle)
        combineList[count++] = list[left++];

    // [Step 3] 오른쪽 배열만 남았을 때 (왼쪽은 소진됨)
    while (right <= end)
        combineList[count++] = list[right++];

    // 원래 배열의 start 위치부터 차례대로 덮어쓰기
    for (int i = 0; i < count; i++)
        list[start + i] = combineList[i];

    delete[] combineList; // 메모리 해제 필수
}

---

✅ 주요 문법 및 개념 정리

구문 논리적 의미 실제 코드 구현

양쪽 비교 가능	left가 중간을 안 넘고, right가 끝을 안 넘음	left <= middle && right <= end
왼쪽 잔여 확인	left 포인터가 middle 인덱스 이하인가?	left <= middle
범위 내 개수	시작부터 끝까지 포함된 정수의 개수	end - start + 1
위치 보정	원본 배열의 특정 부분 구간에 저장	list[start + i]

💡 사고의 전환 : 논리 → 코드

• *"오른쪽 배열이 비어있지 않다"**는 말은 곧 **"현재 가리키는 right 인덱스가 끝(end)보다 작거나 같다"**는 뜻입니다.
• 이러한 추상적 상황을 구체적인 비교 연산자로 바꾸는 연습이 복잡한 알고리즘 구현의 핵심입니다.

---

✨ 느낀 점

• 말로 된 상황을 정확한 조건식으로 바꾸는 능력이 단순한 문법 암기보다 훨씬 중요하다는 것을 깨달음
• 인덱스 범위를 머릿속으로만 생각하지 않고, 직접 그림을 그리며 start, middle, end의 경계를 확인하는 습관이 논리적 오류를 줄이는 데 큰 도움이 됨
• 코드를 단순히 복제하는 것이 아니라, 상황(양쪽 비교, 한쪽 잔여)에 맞는 while문을 스스로 구성해 보며 알고리즘 설계의 자신감을 얻음
• start + i와 같은 세밀한 인덱스 조정이 없으면 정렬 결과가 엉뚱한 곳에 저장된다는 점을 통해 꼼꼼한 코드 작성의 중요성을 체감함