マージソート

main.c

#include "merge_sort.h"


/*
配列の要素を出力
*/
void print_array(const int* array, size_t size)
{
	size_t i;

	for (i = 0; i < size; ++i) {
		printf("%d ", array[i]);
	}
	printf("\n");
}

//比較関数
int compare_int(const void *a, const void *b)
{
	return *(int*)a - *(int*)b;
}

int main(void)
{
	int array[] = { 7, 2, 9, 6, 4, 3, 8, 1, 5 };

	print_array(array, SIZE_OF_ARRAY(array));
	merge_sort(array, SIZE_OF_ARRAY(array), compare_int);
	print_array(array, SIZE_OF_ARRAY(array));

	return 0;
}

merge_sort.c

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


static void merge_sort_rec(int* array, int begin, int end, int* work, int(*func)(const void *, const void *));
static void merge(int* array, int begin, int end, int mid, int* work, int(*func)(const void *, const void *));
static void print_array(const int* array, size_t size);


/*
マージソート
*/
void merge_sort(void* array, size_t size, int(*func)(const void *, const void *))
{
	int* work;

	/* 作業用領域を確保 */
	work = malloc(sizeof(int) * size);

	/* 配列全体を対象にする */
	merge_sort_rec(array, 0, size - 1, work, func);

	free(work);
}

/*
マージソート (再帰部分)
*/
static void merge_sort_rec(int* array, int begin, int end, int* work, int(*func)(const void *, const void *))
{
	int mid;

	/* 要素が１つしかなければ終了 */
	if (begin >= end) {
		return;
	}


	/* ２つのデータ列に分割して、それぞれを再帰的に処理 */
	mid = (begin + end) / 2;
	merge_sort_rec(array, begin, mid, work, func);
	merge_sort_rec(array, mid + 1, end, work, func);

	/* マージ */
	merge(array, begin, end, mid, work, func);
}

/*
マージ
*/
static void merge(int* array, int begin, int end, int mid, int* work, int(*func)(const void *, const void *))
{
	int i, j, k;

	/* 前半の要素を作業用配列へ */
	for (i = begin; i <= mid; ++i) {
		work[i] = array[i];
	}

	/* 後半の要素を逆順に作業用配列へ */
	for (i = mid + 1, j = end; i <= end; ++i, --j) {
		work[i] = array[j];
	}

	/* 作業用配列の両端から取り出した要素をマージ */
	i = begin;
	j = end;
	for (k = begin; k <= end; ++k) {
		/* 昇順にソートするので、小さい方の要素を結果の配列へ移す。 */
		//if (work[i] <= work[j]) { /* == の場合は先頭を優先すると安定なソートになる */
		if (func(&(work[i]), &(work[j])) <= 0) { /* == の場合は先頭を優先すると安定なソートになる */
			array[k] = work[i];
			++i;
		}
		else {
			array[k] = work[j];
			--j;
		}
	}
}

merge_sort.h

#pragma once

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

void merge_sort(void* array, size_t size, int(*func)(const void *, const void *));

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))