マージソートの練習

merge_sort.c

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

void merge_sort(int* data, int size);
void merge(int* data1, int size1, int* data2, int size2, int* result);

void merge_sort(int* data, int size)
{
  int size1, size2;

  if (size <= 1)
    return;

  size1 = size / 2;
  size2 = size - size1;
  merge_sort(data, size1);
  merge_sort(data + size1, size2);
  
  merge(data, size1, data + size1, size2, data);
}

void merge(int* data1, int size1, int* data2, int size2, int* result)
{
  int i1, i2;
  i1 = i2 = 0;
  int* tmp = (int *)malloc(sizeof(int) * (size1 + size2));

  while (i1 < size1 && i2 < size2) {
    if (*(data1 + i1) < *(data2 + i2)) {
      *(tmp + i1 + i2) = *(data1 + i1);
      i1++;
    }
    else {
      *(tmp + i1 + i2) = *(data2 + i2);
      i2++;
    }
  }

  if (i1 == size1)
    for (; i2 < size2; i2++)
      *(tmp + size1 + i2) = *(data2 + i2);
  else
    for (; i1 < size1; i1++)
      *(tmp + i1 + size2) = *(data1 + i1);

  for (i1 = 0; i1 < size1; i1++)
    *(data1 + i1) = *(tmp + i1);
  for (i2 = 0; i2 < size1; i2++)
    *(data2 + i2) = *(tmp + size1 + i2);

  free(tmp);
}

int main(int argc, char *argv[])
{
  int a[] = {3, 1, 4, 1, 5, 9};
  int i, size = sizeof(a) / sizeof(a[0]);

  fputs("source: ", stdout);
  for (i = 0; i < size; i++)
    printf("%d ", *(a + i));
  puts("");
  
  merge_sort(a, size);
  fputs("result: ", stdout);
  for (i = 0; i < size; i++)
    printf("%d ", *(a + i));
  puts("");

  return 0;
}