221 ucx_array_at(*array, rightstart), data) <= 0) { |
221 ucx_array_at(*array, rightstart), data) <= 0) { |
222 /* already sorted */ |
222 /* already sorted */ |
223 return; |
223 return; |
224 } |
224 } |
225 |
225 |
226 // we need memory for one element |
226 /* we need memory for one element */ |
227 void *value = malloc(array->elemsize); |
227 void *value = malloc(array->elemsize); |
228 |
228 |
229 while (start <= mid && rightstart <= end) { |
229 while (start <= mid && rightstart <= end) { |
230 if (cmpfnc(ucx_array_at(*array, start), |
230 if (cmpfnc(ucx_array_at(*array, start), |
231 ucx_array_at(*array, rightstart), data) <= 0) { |
231 ucx_array_at(*array, rightstart), data) <= 0) { |
232 start++; |
232 start++; |
233 } else { |
233 } else { |
234 // save the value from the right |
234 /* save the value from the right */ |
235 memcpy(value, ucx_array_at(*array, rightstart), array->elemsize); |
235 memcpy(value, ucx_array_at(*array, rightstart), array->elemsize); |
236 |
236 |
237 // shift all left elements one element to the right |
237 /* shift all left elements one element to the right */ |
238 size_t shiftcount = rightstart-start; |
238 size_t shiftcount = rightstart-start; |
239 void *startptr = ucx_array_at(*array, start); |
239 void *startptr = ucx_array_at(*array, start); |
240 void *dest = ucx_array_at(*array, start+1); |
240 void *dest = ucx_array_at(*array, start+1); |
241 memmove(dest, startptr, shiftcount*array->elemsize); |
241 memmove(dest, startptr, shiftcount*array->elemsize); |
242 |
242 |
243 // bring the first value from the right to the left |
243 /* bring the first value from the right to the left */ |
244 memcpy(startptr, value, array->elemsize); |
244 memcpy(startptr, value, array->elemsize); |
245 |
245 |
246 start++; |
246 start++; |
247 mid++; |
247 mid++; |
248 rightstart++; |
248 rightstart++; |
249 } |
249 } |
250 } |
250 } |
251 |
251 |
252 // free the temporary memory |
252 /* free the temporary memory */ |
253 free(value); |
253 free(value); |
254 } |
254 } |
255 |
255 |
256 static void ucx_array_mergesort(UcxArray *array, cmp_func cmpfnc, void *data, |
256 static void ucx_array_mergesort(UcxArray *array, cmp_func cmpfnc, void *data, |
257 size_t l, size_t r) { |
257 size_t l, size_t r) { |