정렬된 두 배열 병합하기

문제

merge_arrays() 함수는 오름차순으로 정렬된 두 정수 배열과 각 배열의 길이를 인자로 받는다.
두 배열을 병합하여 오름차순으로 정렬된 새로운 배열을 반환하시오.
단, 함수 내에서 별도의 정렬 함수를 사용해서는 안 된다.

int* merge_arrays(const int arr1[], int arr1_len, const int arr2[], int arr2_len);

arr1	arr2	result
[1, 4, 8, 20]	[2, 3, 10, 16, 22]	[1, 2, 3, 4, 8, 10, 16, 20, 22]
[1, 3, 3]	[2, 3, 4]	[1, 2, 3, 3, 3, 4]
[]	[]	[]
[1, 4, 8, 20]	[]	[1, 4, 8, 20]
[]	[2, 3, 10, 16, 22]	[2, 3, 10, 16, 22]

풀이

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

int* merge_arrays(const int arr1[], int arr1_len, const int arr2[], int arr2_len)
{
    int total_len = arr1_len + arr2_len;

    if (total_len == 0)
        return NULL;

    int* merged = malloc(sizeof(int) * total_len);

    int arr1_index = 0;
    int arr2_index = 0;
    int merged_index = 0;

    while (arr1_index < arr1_len && arr2_index < arr2_len)
    {
        if (arr1[arr1_index] <= arr2[arr2_index])
            merged[merged_index++] = arr1[arr1_index++];
        else
            merged[merged_index++] = arr2[arr2_index++];
    }

    while (arr1_index < arr1_len)
        merged[merged_index++] = arr1[arr1_index++];

    while (arr2_index < arr2_len)
        merged[merged_index++] = arr2[arr2_index++];

    return merged;
}

int main(void)
{
    int arr1[] = { 1, 4, 8, 20 };
    int arr2[] = { 2, 3, 10, 16, 22 };
    int arr1_len = sizeof(arr1) / sizeof(arr1[0]);
    int arr2_len = sizeof(arr2) / sizeof(arr2[0]);
    int total_len = arr1_len + arr2_len;
    int* merged = merge_arrays(arr1, arr1_len, arr2, arr2_len);

    printf("[");

    for (int i = 0; i < total_len; i++)
        printf("%d%s", merged[i], i < total_len - 1 ? ", " : "");

    printf("]\n");
    free(merged);

    return 0;
}

두 배열은 각각 오름차순으로 정렬되어 있을 뿐, 두 배열 사이의 대소 관계는 보장되지 않는다.
arr1의 모든 원소가 arr2의 원소보다 작다고 할 수 없으므로 두 배열을 그대로 이어 붙일 수는 없다.
그래서 각 배열에서 아직 옮기지 않은 첫 원소를 비교해 더 작은 값을 merged에 넣고, 선택한 배열의 인덱스만 증가시킨다.
첫 번째 while 문은 두 배열 중 한쪽의 원소를 모두 옮길 때까지, 두 배열에 남아 있는 원소 중 가장 작은 값을 merged에 차례대로 담는다.

두 배열의 길이와 원소 구성이 다르기 때문에 어느 쪽이 먼저 끝날지는 미리 알 수 없다.
첫 번째 while 문이 끝나면 한쪽 배열의 원소는 모두 옮겨졌지만, 다른 쪽 배열에는 아직 옮기지 않은 원소가 남아 있다.
남은 원소는 이미 merged에 담긴 값보다 크거나 같으므로, 순서대로 merged에 옮기면 병합이 완성된다.