title: C++ 11 Multithread Merge Sort
body: <p>I am new in C++11 and I was trying to write an simple program using thread in C++11. I went for merge sort, and the following is my code:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;thread&gt;
  #include &lt;vector&gt;
  using namespace std;
  
  void merge(vector&lt;int&gt;&amp; vec, int start, int mid, int end)
  {
      vector&lt;int&gt; one (vec.begin() + start, vec.begin() + mid + 1);
      vector&lt;int&gt; two (vec.begin() + mid + 1, vec.begin() + end + 1);
  
      int a = 0;
      int b = 0;
      int index = start;
      while (a &lt; one.size() &amp;&amp; b &lt; two.size())
      {
          if (one[a] &lt; two[b])
              vec[index ++] = one[a ++];
          else 
              vec[index ++] = two[b ++];
      }
  
      // merge the left-over elements
      while (a &lt; one.size())
          vec[index ++] = one[a ++];
      while (b &lt; two.size())
          vec[index ++] = two[b ++];
  }
  
  void merge_sort(vector&lt;int&gt;&amp; vec, int start, int end)
  {
  if (start &gt;= end)
      return;
  
  int mid = start + (end - start) / 2;
  
  // multi-thread version
  thread first(merge_sort, vec, start, mid);
  thread second(merge_sort, vec, mid + 1, end);
  first.join();
  second.join();
  
  /*
  // single-thread version, testified.
  merge_sort(vec, start, mid);
  merge_sort(vec, mid + 1, end); 
  */
  
  merge(vec, start, mid, end);
  }
  
  
  int main()
  {
      int a[] = {4, 2, 5, 9, 7, 1, 3};
      vector&lt;int&gt; vec(a, a + 7);
      merge_sort(vec, 0, 6);
      for (int i = 0; i &lt; 7; i ++)
          cout &lt;&lt; vec[i] &lt;&lt; endl;
      return 0;
  }
  </code></pre>
  
  <p>The underlying algorithm is really simple: after an array is split into two subarrays, two threads were created to take care of the subarrays, one thread for one subarray. After joining the two threads, the two subarray are merged.
  When I tried to compiles it with clang++ 5.1 on MacOS 10.9.4, the following error came out:</p>
  
  <pre><code>Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../lib/c++/v1/thread:332:5:
  error: attempt to use a deleted function
  __invoke(_VSTD::move(_VSTD::get&lt;0&gt;(__t)), _VSTD::move(_VSTD::get&lt;_Indices&gt;(__t))...);
  </code></pre>
  
  <p>Then I went online and found a similar program that uses pthread, instead of C++11 thread, with almost the same underlying logic. I compiled and ran the program, and it worked. It looks like this:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;pthread.h&gt;
  #include &lt;iostream&gt;
  using namespace std;
  
  #define N 2  /* # of thread */
  
  int a[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};  /* target array */
  
  /* structure for array index
   * used to keep low/high end of sub arrays
   */
  typedef struct Arr {
      int low;
      int high;
  } ArrayIndex;
  
  void merge(int low, int high)
  {
          int mid = (low+high)/2;
          int left = low;
          int right = mid+1;
  
          int b[high-low+1];
          int i, cur = 0;
  
          while(left &lt;= mid &amp;&amp; right &lt;= high) {
                  if (a[left] &gt; a[right])
                          b[cur++] = a[right++];
                  else
                          b[cur++] = a[right++];
          }
  
          while(left &lt;= mid) b[cur++] = a[left++];
          while(right &lt;= high) b[cur++] = a[left++];
          for (i = 0; i &lt; (high-low+1) ; i++) a[low+i] = b[i];
  }
  
  void * mergesort(void *a)
  {
          ArrayIndex *pa = (ArrayIndex *)a;
          int mid = (pa-&gt;low + pa-&gt;high)/2;
  
          ArrayIndex aIndex[N];
          pthread_t thread[N];
  
          aIndex[0].low = pa-&gt;low;
          aIndex[0].high = mid;
  
          aIndex[1].low = mid+1;
          aIndex[1].high = pa-&gt;high;
  
          if (pa-&gt;low &gt;= pa-&gt;high) return 0;
  
          int i;
          for(i = 0; i &lt; N; i++) pthread_create(&amp;thread[i], NULL, mergesort, &amp;aIndex[i]);
          for(i = 0; i &lt; N; i++) pthread_join(thread[i], NULL);
  
          merge(pa-&gt;low, pa-&gt;high);
  
          //pthread_exit(NULL);
          return 0;
  }
  
  int main()
  {
          ArrayIndex ai;
          ai.low = 0;
          ai.high = sizeof(a)/sizeof(a[0])-1;
          pthread_t thread;
  
          pthread_create(&amp;thread, NULL, mergesort, &amp;ai);
          pthread_join(thread, NULL);
  
          int i;
          for (i = 0; i &lt; 10; i++) printf ("%d ", a[i]);
          cout &lt;&lt; endl;
  
          return 0;
  }
  </code></pre>
  
  <p>Does anybody know what was wrong with my program?</p>