title: Merge Sort with PThreads in C
body: <p>Side Note: I'm beginning to learn how to use pthreads and I'm starting to get the concept. I've been using this example script (written in C++) here to manage a Merge Sort with threads: <a href="https://www.geeksforgeeks.org/merge-sort-using-multi-threading/" rel="nofollow noreferrer">https://www.geeksforgeeks.org/merge-sort-using-multi-threading/</a></p>
  
  <p>Since I'm writing my own merge sort in C rather than C++, I rewrote this example script to test and noticed an issue. Rather than <code>MAX 20</code> for an array of 20 elements, I decided to go with 15. I noticed that the sorting/merging is invalid (yet somewhat close) and I cannot figure out why... In addition, I've altered the code to use a different amount of threads instead of <code>THREAD_MAX 4</code> so I may change it to 5 or 10 threads.</p>
  
  <p>Could it be the Merge that's yielding invalid results? I've commented it below within main().</p>
  
  <p><strong>My C++ to C convert below:</strong></p>
  
  <pre><code>#include &lt;pthread.h&gt;
  #include &lt;time.h&gt;
  #include &lt;stdlib.h&gt;
  
  // number of elements in array
  #define MAX 15
  
  // number of threads
  #define THREAD_MAX 4
  
  //using namespace std;
  
  // array of size MAX
  int a[MAX];
  int part = 0;
  
  // merge function for merging two parts
  void merge(int low, int mid, int high)
  {   
      int* left = (int*) malloc( (mid - low + 1) * sizeof(int));
      int* right = (int*) malloc( (high - mid) * sizeof(int));
  
  
      // n1 is size of left part and n2 is size
      // of right part
      int n1 = mid - low + 1,
      n2 = high - mid,
      i, j;
  
      // storing values in left part
      for (i = 0; i &lt; n1; i++)
          left[i] = a[i + low];
  
      // storing values in right part
      for (i = 0; i &lt; n2; i++)
          right[i] = a[i + mid + 1];
  
      int k = low;
      i = j = 0;
  
      // merge left and right in ascending order
      while (i &lt; n1 &amp;&amp; j &lt; n2) {
          if (left[i] &lt;= right[j])
              a[k++] = left[i++];
          else
              a[k++] = right[j++];
      }
  
      // insert remaining values from left
      while (i &lt; n1) {
          a[k++] = left[i++];
      }
  
      // insert remaining values from right
      while (j &lt; n2) {
          a[k++] = right[j++];
      }
  
      free(left);
      free(right);
  }
  
  // merge sort function
  void merge_sort(int low, int high)
  {
      // calculating mid point of array
      int mid = low + (high - low) / 2;
      if (low &lt; high) {
  
          // calling first half
          merge_sort(low, mid);
  
          // calling second half
          merge_sort(mid + 1, high);
  
          // merging the two halves
          merge(low, mid, high);
      }
  }
  
  // thread function for multi-threading
  void* merge_sort123(void* arg)
  {
      // which part out of 4 parts
      int thread_part = part++;
  
      // calculating low and high
      int low = thread_part * (MAX / THREAD_MAX);
      int high = (thread_part + 1) * (MAX / THREAD_MAX) - 1;
  
      // evaluating mid point
      int mid = low + (high - low) / 2;
      if (low &lt; high) {
          merge_sort(low, mid);
          merge_sort(mid + 1, high);
          merge(low, mid, high);
      }
      return 0;
  }
  
  
  
  // Driver Code
  int main()
  {
      // generating random values in array
      for (int i = 0; i &lt; MAX; i++){
          a[i] = rand() % 100;
      //        printf("%d ", a[i]);
      }
  
  
      pthread_t threads[THREAD_MAX];
  
      // creating 4 threads
      for (int i = 0; i &lt; THREAD_MAX; i++)
          pthread_create(&amp;threads[i], NULL, merge_sort123,
                         (void*)NULL);
  
      // joining all 4 threads
      for (int i = 0; i &lt; THREAD_MAX; i++)
          pthread_join(threads[i], NULL);
  
  
      ///////////////////////////////////////////////////////////////
      // --- THIS MAY BE THE PART WHERE THE MERGING IS INVALID --- //
      ///////////////////////////////////////////////////////////////
      // merging the final 4 parts
      merge(0, (MAX / 2 - 1) / 2, MAX / 2 - 1);
      merge(MAX / 2, MAX/2 + (MAX-1-MAX/2)/2, MAX - 1);
      merge(0, (MAX - 1)/2, MAX - 1);
  
  
      // displaying sorted array
      printf("\n\nSorted array: ");
      for (int i = 0; i &lt; MAX; i++)
          printf ("%d ", a[i]);
  
  
      printf("\n");
      return 0;
  }
  </code></pre>