fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <windows.h>
  5. #include <process.h>
  6.  
  7. void merge(int L[], int left_count, int R[], int right_count, int out[])
  8. {
  9. 	int left_iter = 0, right_iter = 0, out_iter = 0;
  10.  
  11. 	while(left_iter < left_count && right_iter < right_count)
  12. 	{
  13. 		if(L[left_iter] <= R[right_iter])
  14. 			out[out_iter] = L[left_iter++];
  15. 		else
  16. 			out[out_iter] = R[right_iter++];
  17. 		out_iter++;
  18. 	}
  19.  
  20. 	// Process the rest of elements
  21. 	if(left_iter == left_count)
  22. 		while (out_iter < (left_count + right_count))
  23. 			out[out_iter++] = R[right_iter++];
  24. 	else
  25. 		while (out_iter < (left_count + right_count))
  26. 			out[out_iter++] = L[left_iter++];
  27. }
  28.  
  29. void mergesort(int a[], int n)
  30. {
  31. 	int i;
  32. 	int split = n / 2;
  33. 	int *L = malloc(split * sizeof(int));
  34. 	int *R = malloc((n - split) * sizeof(int));
  35.  
  36. 	if(n > 1)
  37. 	{
  38. 		for(i = 0; i < split; i++)
  39. 			L[i] = a[i];
  40. 		for(i = split; i < n; i++)
  41. 			R[i - split] = a[i];
  42. 		mergesort(L, split);
  43. 		mergesort(R, n - split);
  44. 		merge(L, split, R, n - split, a);
  45. 	}
  46. 	free(L);
  47. 	free(R);
  48. }
  49.  
  50. struct ThreadData
  51. {
  52. 	int  *array;
  53. 	int   length;
  54. };
  55.  
  56. DWORD WINAPI mergesort_parallel(LPVOID *data)
  57. {
  58. 	int i = 0, length = 0, split = 0;
  59. 	HANDLE hThreadLeft, hThreadRight;
  60.  
  61. 	length = ((struct ThreadData *)data)->length;
  62. 	split  = length / 2;
  63. 	int *L = malloc(split * sizeof(int));
  64. 	int *R = malloc((length - split) * sizeof(int));
  65.  
  66. 	if(length > 1)
  67. 	{
  68. 		for(i = 0; i < split; i++)
  69. 			L[i]		 = ((struct ThreadData *)data)->array[i];
  70. 		for(i = split; i < length; i++)
  71. 			R[i - split] = ((struct ThreadData *)data)->array[i];
  72.  
  73. 		struct ThreadData thread_L = { L, split };
  74. 		struct ThreadData thread_R = { R, length - split };
  75.  
  76. 		hThreadLeft  = (HANDLE)_beginthreadex(NULL, 0, &mergesort_parallel,
  77. 											  (void *)&thread_L, 0, NULL);
  78. 		hThreadRight = (HANDLE)_beginthreadex(NULL, 0, &mergesort_parallel,
  79. 											  (void *)&thread_L, 0, NULL);
  80. 		WaitForSingleObject(hThreadLeft, INFINITE);
  81. 		WaitForSingleObject(hThreadRight, INFINITE);
  82.  
  83. 		merge(L, split, R, length - split, ((struct ThreadData *)data)->array);
  84.  
  85. 		CloseHandle(hThreadLeft);
  86. 		CloseHandle(hThreadRight);
  87. 	}
  88. 	free(L);
  89. 	free(R);
  90. 	return 0;
  91. }
  92.  
  93. int main(int argc, char *argv[]){
  94. 	int i;
  95. 	DWORD ticks = 0;
  96. 	const int size = 100000;
  97. 	int v[size]; /*= {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};*/
  98. 	for (i = 0; i < size; ++i)
  99. 		v[i] = i % 11;
  100.  
  101. 	/*printf("Source array:\n");
  102. 	for(i = 0; i < size; i++)
  103. 		printf("%d ", v[i]);
  104. 	putchar('\n');*/
  105. 	struct ThreadData td = { (int *)&v, size };
  106.  
  107. 	ticks = GetTickCount();
  108. 	//mergesort(v, size);
  109. 	mergesort_parallel((void *)&td);
  110. 	printf("Time elapsed: %d millis\n", GetTickCount() - ticks);
  111.  
  112. 	/*printf("Sorted array:\n");
  113. 	for(i = 0; i < size; i++)
  114. 		printf("%d ", v[i]);*/
  115.  
  116. 	printf("\nFinished\n");
  117.  
  118. 	scanf("%d", &i);
  119. 	return 0;
  120. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.c:4:21: fatal error: windows.h: No such file or directory
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/jALSNb
language:
C (gcc 8.3)
created:
9 years ago
visibility:
secret

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!