[C/알고리즘] 병합 정렬 Merge Sort

//병합 정렬 알고리즘: mergeSort.c
// 유튜브 참고 영상: "동빈나"의 "8강 - 병합 정렬(Merge Sort) [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #8 ]"

#include <stdio.h>
#include <stdlib.h>

#define NUM_ARRAY   100

void printArray(int arr[], int length) {
    for (int i = 0; i< length; i++) {
        printf("%d\n", arr[i]);
    }
    printf("\n");
}

int number = NUM_ARRAY;
int sorted[NUM_ARRAY]; //정렬배열은 반드시 전역 변수로...

void merge(int arr[], int start, int mid, int end) {
    int pos1 = start;
    int pos2 = mid + 1;
    int count = start;
    while (pos1 <= mid && pos2 <=end) {
        if (arr[pos1] <= arr[pos2]) {
            sorted[count] = arr[pos1];
            pos1++;
        } else {
            sorted[count] = arr[pos2];
            pos2 ++;
        }
        count++;
    }
    if(pos1 > mid) {
        for(int i = pos2; i <= end; i++) {
            sorted[count] = arr[i];
            count++;
        }
    } else {
        for (int i = pos1; i <= mid; i++) {
            sorted[count] = arr[i];
            count++;
        }
    }
    //정렬된 임시 배열을 원 배열에 삽입
    for (int i = start; i<= end; i++) {
        arr[i] = sorted[i];
     }
}  

void mergeSort(int arr[], int start, int end) {
    // 크기가 1보다 큰 경우
    if (start < end) {
        int mid = (start + end) /2;
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
}

int main() {

    //int array[] = {1, 4, 7, 10, 15, 3, 5, 11, 13, 14, 17, 21}; 
    int array[NUM_ARRAY];
    
    for (int i = 0; i < NUM_ARRAY; i++)
        array[i] = rand();

    const int len = sizeof(array) / sizeof(int);
    int start = 0;
    int end = len -1;
    int mid = (start + end) / 2;

    //printf("%d, %d, %d, %d\n", len, start, mid, end);
    mergeSort(array, start, end);

    printArray(sorted, len);
    return 0;
}
----------------- 실행 결과 ------------
35005211
42999170
84353895
135497281
137806862
149798315
184803526
233665123
.........
1973594324
1984210012
1998898814
2001100545
2038664370
2044897763
2053999932
2084420925
2089018456
2145174067