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, 1); // 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 4392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 972  794  841   73  711  866  664  329 
 612  592  653  424   84  255  751 
Starting subthread...
Finished subthread.
  73   84  255  329  424  592  612  653 
 664  711  751  794  841  866  972
https://ideone.com/VaddJ3
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!