55 lines
1.8 KiB
C
55 lines
1.8 KiB
C
#include <c_MergeSort.h>
|
|
|
|
/**
|
|
* Internal merging routine for top-down merge sort.
|
|
*/
|
|
C_STATIC_FORCE_INLINE
|
|
void c_MergeInternal(char* arr, c_size_t left, c_size_t mid, c_size_t right,
|
|
c_size_t size, char* aux,
|
|
int (*compar)(const void*, const void*)) {
|
|
c_size_t i = left;
|
|
c_size_t j = mid + 1;
|
|
c_size_t k = left;
|
|
|
|
// Copy the target segment into the auxiliary working buffer
|
|
memcpy(aux + (left * size), arr + (left * size), (right - left + 1) * size);
|
|
|
|
// Merge back into the original array tracking sorted boundaries
|
|
while (i <= mid && j <= right) {
|
|
if (compar(aux + (i * size), aux + (j * size)) <= 0) {
|
|
memcpy(arr + (k * size), aux + (i * size), size);
|
|
i++;
|
|
} else {
|
|
memcpy(arr + (k * size), aux + (j * size), size);
|
|
j++;
|
|
}
|
|
k++;
|
|
}
|
|
|
|
// Copy any remaining elements of the left sub-array if any
|
|
while (i <= mid) {
|
|
memcpy(arr + (k * size), aux + (i * size), size);
|
|
i++;
|
|
k++;
|
|
}
|
|
// Note: Remaining items on the right side are already natively sitting in the correct slots.
|
|
}
|
|
|
|
/**
|
|
* Recursive structural block splitting segments into halves.
|
|
*/
|
|
void c_MergeSortSub(char* arr, c_size_t left, c_size_t right, c_size_t size, char* aux,
|
|
int (*compar)(const void*, const void*)) {
|
|
if (left >= right) return;
|
|
|
|
c_size_t mid = left + (right - left) / 2;
|
|
|
|
c_MergeSortSub(arr, left, mid, size, aux, compar);
|
|
c_MergeSortSub(arr, mid + 1, right, size, aux, compar);
|
|
|
|
// Optimization: If the array segment is already naturally sorted, skip the merge routine
|
|
if (compar(arr + (mid * size), arr + ((mid + 1) * size)) > 0) {
|
|
c_MergeInternal(arr, left, mid, right, size, aux, compar);
|
|
}
|
|
}
|