壊れてた並列クイックソートが直った？

pthreadで並列化したつもりのクイックソートが微妙に壊れていた。

$ ./psort 10
0:3:5:6:9:7:6:6:3:2:
--sort--
0:2:3:3:6:5:6:6:7:9:
$ ./psort 20
19:18:7:5:4:8:13:10:17:1:2:7:15:4:10:7:9:6:6:2:
--sort--
1:2:2:5:4:8:13:10:17:19:7:7:15:4:10:7:9:6:6:18:
$ ./psort 30
20:12:0:11:20:17:15:10:21:15:20:23:2:19:11:18:17:26:11:19:0:9:3:21:28:13:17:16:20:1:
--sort--
0:0:3:9:1:11:11:10:2:11:12:17:13:16:15:17:17:15:18:19:20:26:19:21:28:21:23:20:20:20:

並べ替えようというガンバリは感じられるものの、かなり結果がおかしい。シングルスレッドのものとマルチスレッドのもので違うのは以下の部分。

  if (left - part->begin >= 2) {
    pnext->ary = part->ary;
    pnext->begin = part->begin;
    pnext->end = left - 1;
    myqsort(pnext);
  }
  if (part->end - right >= 2) {
    pnext->ary = part->ary;
    pnext->begin = right + 1;
    pnext->end = part->end;
    myqsort(pnext);
  }
(ssort.c)

------------------------------

#include <pthread.h>
#define NUM_THREADS 3

    :
    :

  if (left - part->begin >= 2) {
    pnext->ary = part->ary;
    pnext->begin = part->begin;
    pnext->end = left - 1;
    thread1 = pthread_create(&threads[t++], NULL, myqsort, (void *)pnext);
  }
  if (part->end - right >= 2) {
    pnext->ary = part->ary;
    pnext->begin = right + 1;
    pnext->end = part->end;
    thread2 = pthread_create(&threads[t++], NULL, myqsort, (void *)pnext);
  }
}
(psort.c)

ソート結果の壊れ方からして、いかにもスレッド実行のタイミング制御の問題っぽくて、「そういえばjoinしてなかったのはやっぱりダメだったのか」と、thread_joinをつけてみた。

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

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

typedef struct {
  int *ary;
  int begin;
  int end;
} partition;

partition *init_part(void) {
  return malloc(sizeof(partition));
}

void *myqsort(void *p) {

  pthread_t thread1, thread2; 
  long t = 0;
  thread1 = thread2 = 0;

  partition *part, *pnext;
  part = init_part();
  pnext = init_part();

  part = (partition *)p;

  int left = part->begin;
  int right = part->end;

  if (left >= right) {
    pthread_exit(NULL);
  }

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

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

  if (left - part->begin >= 2) {
    pnext->ary = part->ary;
    pnext->begin = part->begin;
    pnext->end = left - 1;
    pthread_create(&thread1, NULL, myqsort, (void *)pnext);
  }
  if (part->end - right >= 2) {
    pnext->ary = part->ary;
    pnext->begin = right + 1;
    pnext->end = part->end;
    pthread_create(&thread2, NULL, myqsort, (void *)pnext);
  }
  if (thread1) pthread_join(thread1, NULL); 
  if (thread2) pthread_join(thread2, NULL); 
  pthread_exit(NULL);
}

とりあえずソートはできているけど、どうも何かがヘンな気がする。オライリーから出ているpthreadの本を買ってみた。