配列マージの基本

マージソートの核となる処理は、すでに整列済みの2つの部分配列を効率的に結合することです。たとえば、ar1[] = {1,2,3,4} と ar2[] = {3,4,5,6,7} の2つの配列があるとします。これらを効率的にマージするには、それぞれの配列にポインタを用意しておき、値を比較しながら新しい配列に格納していきます。

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

int main() {
    int ar1[] = {1, 2, 3, 4};
    int ar2[] = {3, 4, 5, 6, 7};
    int sz1 = sizeof(ar1) / sizeof(int);
    int sz2 = sizeof(ar2) / sizeof(int);
    int* merged = (int*)malloc(sizeof(int) * (sz1 + sz2));
    assert(merged);

    int i = 0, j = 0, k = 0;

    while (i < sz1 && j < sz2) {
        if (ar1[i] < ar2[j]) {
            merged[k++] = ar1[i++];
        } else {
            merged[k++] = ar2[j++];
        }
    }

    while (i < sz1) merged[k++] = ar1[i++];
    while (j < sz2) merged[k++] = ar2[j++];

    for (int idx = 0; idx < sz1 + sz2; idx++) {
        printf("%d ", merged[idx]);
    }

    free(merged);
    return 0;
}

ソートアルゴリズムの構造

このマージ処理を応用して、未整列の配列全体をソートするには、再帰的に配列を分割し、それぞれをソートしてからマージします。最終的には、要素数1の配列（それ自身が整列済み）まで分割し、そこから再帰的にマージすることで全体の整列が実現されます。

再帰による実装

再帰的に実装する場合、配列を中央で分割し、それぞれの部分を再帰的にソートした後にマージします。この方法は、二分木の後行順序走査に似ています。

void mergeSort(int* arr, int* temp, int left, int right) {
    if (left >= right) return;

    int mid = (left + right) / 2;
    mergeSort(arr, temp, left, mid);
    mergeSort(arr, temp, mid + 1, right);

    int i = left, j = mid + 1, k = left;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    for (int idx = left; idx <= right; idx++) {
        arr[idx] = temp[idx];
    }
}

void mergeSortDriver(int* arr, int size) {
    int* temp = (int*)malloc(sizeof(int) * size);
    assert(temp);
    mergeSort(arr, temp, 0, size - 1);
    free(temp);
}

非再帰による実装

スタックオーバーフローを防ぐために、再帰を使わず反復的に実装する方法もあります。これは、分割サイズ（gap）を2倍ずつ広げながら、各ブロック内でマージを行う方法です。

void mergeSortIterative(int* arr, int size) {
    int* temp = (int*)malloc(sizeof(int) * size);
    assert(temp);

    for (int gap = 1; gap < size; gap *= 2) {
        for (int i = 0; i < size; i += 2 * gap) {
            int left = i;
            int mid = i + gap - 1;
            int right = i + 2 * gap - 1;

            if (mid >= size) mid = size - 1;
            if (right >= size) right = size - 1;

            int l = left, r = mid + 1, k = left;

            while (l <= mid && r <= right) {
                if (arr[l] <= arr[r]) {
                    temp[k++] = arr[l++];
                } else {
                    temp[k++] = arr[r++];
                }
            }

            while (l <= mid) temp[k++] = arr[l++];
            while (r <= right) temp[k++] = arr[r++];

            for (int idx = left; idx <= right; idx++) {
                arr[idx] = temp[idx];
            }
        }
    }

    free(temp);
}

実装上の注意点

• 一時配列（temp）は、マージ処理中に結果を格納するために必要です。
• 境界条件（部分配列の範囲外アクセス）を適切に処理する必要があります。
• メモリコピーにはmemcpyやmemmoveを用いることで効率的に処理できます。