fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <time.h>
  5. #include <pthread.h>
  6.  
  7.  
  8. struct Params
  9. {
  10.     int *start;
  11.     size_t len;
  12.     int depth;
  13. };
  14.  
  15. // only used for synchronizing stdout from overlap.
  16. pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
  17.  
  18. // forward declare our thread proc
  19. void *merge_sort_thread(void *pv);
  20.  
  21.  
  22. // a simple merge algorithm. there are *several* more efficient ways
  23. //  of doing this, but the purpose of this exercise is to establish
  24. //  merge-threading, so we stick with simple for now.
  25. void merge(int *start, int *mid, int *end)
  26. {
  27.     int *res = malloc((end - start)*sizeof(*res));
  28.     int *lhs = start, *rhs = mid, *dst = res;
  29.  
  30.     while (lhs != mid && rhs != end)
  31.         *dst++ = (*lhs < *rhs) ? *lhs++ : *rhs++;
  32.  
  33.     while (lhs != mid)
  34.         *dst++ = *lhs++;
  35.  
  36.     // copy results
  37.     memcpy(start, res, (rhs - start) * sizeof *res);
  38.     free(res);
  39. }
  40.  
  41. // our multi-threaded entry point.
  42. void merge_sort_mt(int *start, size_t len, int depth)
  43. {
  44.     if (len < 2)
  45.         return;
  46.  
  47.     if (depth <= 0 || len < 4)
  48.     {
  49.         merge_sort_mt(start, len/2, 0);
  50.         merge_sort_mt(start+len/2, len-len/2, 0);
  51.     }
  52.     else
  53.     {
  54.         struct Params params = { start, len/2, depth/2 };
  55.         pthread_t thrd;
  56.  
  57.         pthread_mutex_lock(&mtx);
  58.         printf("Starting subthread...\n");
  59.         pthread_mutex_unlock(&mtx);
  60.  
  61.         // create our thread
  62.         pthread_create(&thrd, NULL, merge_sort_thread, &params);
  63.  
  64.         // recurse into our top-end parition
  65.         merge_sort_mt(start+len/2, len-len/2, depth/2);
  66.  
  67.         // join on the launched thread
  68.         pthread_join(thrd, NULL);
  69.  
  70.         pthread_mutex_lock(&mtx);
  71.         printf("Finished subthread.\n");
  72.         pthread_mutex_unlock(&mtx);
  73.     }
  74.  
  75.     // merge the partitions.
  76.     merge(start, start+len/2, start+len);
  77. }
  78.  
  79. // our thread-proc that invokes merge_sort. this just passes the
  80. //  given parameters off to our merge_sort algorithm
  81. void *merge_sort_thread(void *pv)
  82. {
  83.     struct Params *params = pv;
  84.     merge_sort_mt(params->start, params->len, params->depth);
  85.     return pv;
  86. }
  87.  
  88. // public-facing api
  89. void merge_sort(int *start, size_t len)
  90. {
  91.     merge_sort_mt(start, len, 2); // 4 is a nice number, will use 7 threads.
  92. }
  93.  
  94. int main()
  95. {
  96.     static const unsigned int N = 15;
  97.     int *data = malloc(N * sizeof(*data));
  98.     unsigned int i;
  99.  
  100.     srand((unsigned)time(0));
  101.     for (i=0; i<N; ++i)
  102.     {
  103.         data[i] = rand() % 1024;
  104.         printf("%4d ", data[i]);
  105.         if ((i+1)%8 == 0)
  106.             printf("\n");
  107.     }
  108.     printf("\n");
  109.  
  110.     // invoke our multi-threaded merge-sort
  111.     merge_sort(data, N);
  112.     for (i=0; i<N; ++i)
  113.     {
  114.         printf("%4d ", data[i]);
  115.         if ((i+1)%8 == 0)
  116.             printf("\n");
  117.     }
  118.     printf("\n");
  119.  
  120.     free(data);
  121.  
  122.     return 0;
  123.  
  124. }
Success #stdin #stdout 0s 4424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 861  372  374  690  179   22  938  137 
 396  119  721  822  357  745  228 
Starting subthread...
Starting subthread...
Finished subthread.
Starting subthread...
Finished subthread.
Finished subthread.
  22  119  137  179  228  357  372  374 
 396  690  721  745  822  861  938
https://ideone.com/jhY39e
language:
C (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!