11void CRT_qsort(
void *base, uint32_t count, uint32_t element_size, int32_t (*compare)(
void const *,
void const *))
13 if (count < 2 || !element_size)
16 int32_t pending_partition_count = 0;
17 char *first_element = base;
18 char *partition_high_stack[30];
19 char *last_element = (count - 1) * element_size + first_element;
20 char *partition_low_stack[30];
24 uint64_t partition_count = (uint64_t)(uint32_t)(last_element - first_element) / element_size + 1;
26 if (partition_count > 8)
29 (partition_count >> 1) * element_size + first_element,
30 first_element, element_size);
32 char *left_scan = first_element;
33 char *right_scan = &last_element[element_size];
37 left_scan += element_size;
39 if (left_scan <= last_element && compare(left_scan, first_element) <= 0)
42 bool right_at_least_pivot;
46 right_scan -= element_size;
48 if (right_scan <= first_element)
51 right_at_least_pivot = compare(right_scan, first_element) >= 0;
52 }
while (right_at_least_pivot);
54 if (right_scan < left_scan)
57 CRT_swap(left_scan, right_scan, element_size);
60 CRT_swap(first_element, right_scan, element_size);
62 if (right_scan - first_element - 1 < last_element - left_scan)
64 if (left_scan < last_element)
66 partition_low_stack[pending_partition_count] = left_scan;
67 partition_high_stack[pending_partition_count] = last_element;
68 ++pending_partition_count;
71 if (&first_element[element_size] < right_scan)
73 last_element = right_scan - element_size;
80 if (&first_element[element_size] < right_scan)
82 partition_low_stack[pending_partition_count] = first_element;
83 partition_high_stack[pending_partition_count] = right_scan - element_size;
84 ++pending_partition_count;
87 if (left_scan < last_element)
89 first_element = left_scan;
96 CRT_shortsort(first_element, last_element, element_size, compare);
98 if (!pending_partition_count)
101 --pending_partition_count;
102 first_element = partition_low_stack[pending_partition_count];
103 last_element = partition_high_stack[pending_partition_count];
109void CRT_shortsort(
char *first_element,
char *last_element, uint32_t element_size, int32_t (*compare)(
void const *,
void const *))
111 for (
char *unsorted_end = last_element; unsorted_end > first_element; unsorted_end -= element_size)
113 char *maximum_element = first_element;
115 for (
char *candidate = &first_element[element_size]; candidate <= unsorted_end; candidate = &candidate[element_size])
117 if (compare(candidate, maximum_element) > 0)
118 maximum_element = candidate;
121 CRT_swap(maximum_element, unsorted_end, element_size);