2つに分けてソートしてからマージソート

与えられた配列を真ん中で2つに分けて、それぞれを並列にクイックソートしてからマージソートするという方針で書いてみた。といいつつ並列化のところだけ後回し。配列が自分の長さを知らないなんておかしいぞと思ったので、arrayという構造体を定義してみた。しかし、1つのメモリ上のオブジェクトを仮想的に分割して2つのオブジェクトに見立てたりして、なんかお行儀悪い感じ。

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

#define INIT_NUM 0
#define SWAP(type, x, y) do {type tmp = x; x = y; y = tmp;}while(0)

typedef struct {
  int *ary;
  int size;
} array;

array *init_array(int size) {

  array *ptr;
  int i;

  ptr = (array *)malloc(sizeof(array));
  ptr->ary = (int *)malloc(sizeof(int)*size);
  ptr->size = size;

  for (i = 0; i < size; i++) {
    ptr->ary[i] = INIT_NUM;
  }
  return ptr;
}

void show_array(array *p) {
  int i;
  for (i = 0; i < p->size; i++) {
    printf("%d:", p->ary[i]);
  }
  printf("\n");
}

void set_random(array *p) {
  int i;

  for (i = 0; i < p->size; i++) {
    p->ary[i] = (rand() % 100);
  }
}

int intcmp(const void *a, const void *b) {
  return (*(int *)a > *(int *)b);
}

int myqsort(int ary[], int begin, int end) {
  int left = begin;
  int right = end;
  int tmp;

  if (left >= right) {
    return -1;
  }

  int pivot = ary[(left + right) / 2];
  
  while (1) {
    while(ary[left] < pivot) {
      left++;
    }
    while(ary[right] > pivot) {
      right--;
    }
    if (left >= right) {
      break;
    }

    SWAP(int, ary[left], ary[right]);
    left++;
    right--;
  }

  if (left - begin >= 2) {
    myqsort(ary, begin, left - 1);
  }
  if (end - right >= 2) {
    myqsort(ary, right + 1, end);
  }
}

array *msort(array *p1, array *p2) {
  array *new;
  int i, j, k;
  i = j = k = 0;

  new = init_array(p1->size + p2->size);
  
  while ((i < p1->size) && (j < p2->size)) {
    if (p1->ary[i] < p2->ary[j]) {
      new->ary[k++] = p1->ary[i++];
    } else {
      new->ary[k++] = p2->ary[j++];
    }
  }

   while (i < p1->size)
     new->ary[k++] = p1->ary[i++];
   while (j < p2->size)
     new->ary[k++] = p2->ary[j++];

  return new;
}

array *psort(array *p) {
  int center;
  array *a, *b, *c;
  int ret1, ret2;

  a = (array *)malloc(sizeof(array));
  b = (array *)malloc(sizeof(array));

  if (p->size == 1) return;
  if (p->size < 10) {
    qsort(p->ary, p->size, sizeof(int), intcmp);
  }

  center = p->size / 2;

  a->ary = p->ary;
  a->size = center;

  b->ary = p->ary + center;
  b->size = p->size - center;

  myqsort(a->ary, 0, a->size - 1); // This can be parallelized.
  myqsort(b->ary, 0, b->size - 1); //

  c = msort(a, b);

  free(a); free(b);
  return c;
}

int main (int argc, char *argv[]) {

  array *a, *b, *c;
  int i, j, size;

  srand(time(NULL));

  if (argc <= 1) {
    printf("we need an int parameter\n");
    exit(1);
  }
  size = atoi(argv[1]);

  a = init_array(size);
  set_random(a);
  show_array(a);
  c = psort(a);
  show_array(c);
}