title: Writing a parallel quick sort in c
body: <p>I need to write a parallel quick sort in c using pthreads. This is what I did so far. </p>
  
  <pre><code>    #include &lt;stdio.h&gt;
      #include &lt;stdlib.h&gt;
      #include &lt;string.h&gt;
      #include &lt;pthread.h&gt;
      #include &lt;unistd.h&gt;  // sleep()
      #include &lt;stdio.h&gt;
      #include &lt;stdlib.h&gt;  // EXIT_SUCCESS
      #include &lt;string.h&gt;  // strerror()
      #include &lt;errno.h&gt;
  
      #define SIZE_OF_DATASET 6
      void* quickSort( void* data);
      int partition( int* a, int, int);
  
  
      struct info {
          int start_index;
          int* data_set;
          int end_index;
      };
  
  
  
      int main(int argc, char **argv)
      {
  
          int a[] = { 7, 12, 1, -2,8,2};
          pthread_t thread_id;
          struct info *info = malloc(sizeof(struct info));
          info-&gt;data_set=malloc(sizeof(int)*SIZE_OF_DATASET);
  
          info-&gt;data_set=a;
          info-&gt;start_index=0;
          info-&gt;end_index=SIZE_OF_DATASET-1;
  
          if (pthread_create(&amp;thread_id, NULL, quickSort, info)) {
              fprintf(stderr, "No threads for you.\n");
              return 1;
          }
  
          pthread_join(thread_id, NULL);
  
          printf("\n\nSorted array is:  ");
          int i;
            for(i = 0; i &lt; SIZE_OF_DATASET; ++i)
                 printf(" %d ", info-&gt;data_set[i]);
  
          return 0;
      }
  
      void* quickSort( void *data)
      {
          struct info *info = data;
          int j,l,r;
          l = info-&gt;start_index;
          r = info-&gt;end_index;
  
          pthread_attr_t attr;
          pthread_t thread_id1;
          pthread_t thread_id2;
          pthread_attr_init(&amp;attr);
  
         if( l &lt; r )
         {
  
             j = partition( info-&gt;data_set, l, r);
             info-&gt;start_index=l;
             info-&gt;end_index=j-1;
             if(info-&gt;end_index&lt;0)info-&gt;end_index=0;
  
            if (pthread_create(&amp;thread_id1, NULL, quickSort, info)) {
                  fprintf(stderr, "No threads for you.\n");
                  return NULL;
            }
            info-&gt;start_index=j+1;
            info-&gt;end_index=r;
  
            if (pthread_create(&amp;thread_id2, NULL, quickSort, info)) {
                fprintf(stderr, "No threads for you.\n");
                return NULL;
            }
  
            pthread_join(thread_id1, NULL);
            pthread_join(thread_id2, NULL);
        }
  
      return NULL;
  
      }
  
  
      int partition( int* a, int l, int r) {
         int pivot, i, j, t;
         pivot = a[l];
         i = l; j = r+1;
  
         while( 1)
         {
          do ++i; while( a[i] &lt;= pivot &amp;&amp; i &lt;= r );
          do --j; while( a[j] &gt; pivot );
          if( i &gt;= j ) break;
          t = a[i]; a[i] = a[j]; a[j] = t;
         }
         t = a[l]; a[l] = a[j]; a[j] = t;
         return j;
      }
  </code></pre>
  
  <p>But inside quick sort function only call first thread only. Cant understand what is been happening here. </p>
  
  <p>Note : serial version of code has been tested. no issue with that</p>
  
  <p><strong>UPDATE:</strong> </p>
  
  <p>This is modified version based on John Bollinger's solution. But still second half of array which is taken by newly created thread inside quicksort is not sorted. </p>
  
  <pre><code>   int main(int argc, char **argv)
  {
  
      int a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9,5,3,24,5,23,3,1,56,8,4,34,23,51};
      struct info *info = malloc(sizeof(struct info));
      info-&gt;data_set=malloc(sizeof(int)*SIZE_OF_DATASET);
      info-&gt;data_set=a;
      info-&gt;start_index=0;
      info-&gt;end_index=SIZE_OF_DATASET-1;
  
      quickSort(info);
      printf("\n\nSorted array is:  ");
      int i;
        for(i = 0; i &lt; SIZE_OF_DATASET; ++i)
             printf(" %d ", info-&gt;data_set[i]);
      return 0;
  }
  
  void* quickSort( void *data)
  {
      struct info *info = data;
      struct info *info1 = data;
      int j,l,r;
      l = info-&gt;start_index;
      r = info-&gt;end_index;
  
      pthread_attr_t attr;
      pthread_t thread_id1;
      pthread_attr_init(&amp;attr);
  
     if( l &lt; r )
     {
  
         j = partition( info-&gt;data_set, l, r);
         info1-&gt;start_index=j+1;
         info1-&gt;end_index=r;
         info1-&gt;data_set = info-&gt;data_set;
         if(info1-&gt;end_index&lt;0)info1-&gt;end_index=0;
  
        if (pthread_create(&amp;thread_id1, NULL, quickSort, info1)) {
              fprintf(stderr, "No threads for you.\n");
              return NULL;
        }
        info-&gt;start_index=l;
        info-&gt;end_index=j-1;
  
        if(info-&gt;end_index &lt; 0) info-&gt;end_index = 0;
        quickSort(info);  /* don't care about the return value */
        pthread_join(thread_id1, NULL);
  
    }
  
  return NULL;
  
  }
  </code></pre>